文章基本信息

标题：Measures of Nondeterminism in Finite Automata
本地全文：下载
作者：Juraj Hromkovic ; Juhani Karhumaki ; Hartmut Klauck 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：While deterministic finite automata seem to be well understood, surprisingly many important problems concerning nondeterministic finite automata (nfa's) remain open. One such problem area is the study of different measures of nondeterminism in finite automata and the estimation of the sizes of minimal nondeterministic finite automata. In this paper the concept of communication complexity is applied in order to achieve progress in this problem area. The main results are as follows: 1. Deterministic communication complexity provides lower bounds on the size of unambiguous nfa's. Applying this fact, the proofs of several results about nfa's with limited ambiguity can be simplified. 2. For an nfa A we consider the complexity measures advice_A(n) as the number of advice bits, ambig_A(n) as the number of accepting computations, and leaf_A(n) as the number of computations for worst case inputs of size n. These measures are correlated as follows (assuming that the nfa A is minimal): advice_A(n), ambig_A(n) lower-equal leaf_A(n) lower-equal O(advice_A(n) times ambig_A(n)). 3. leaf_A(n) is always either a constant, between linear and polynomial in n, or exponential in n. 4. There is a family of languages KON_{k^2} with an exponential size gap between nfa's with polynomial leaf number/ambiguity and nfa's with ambiguity k. This partially provides an answer to the open problem posed by Ravikumar and Ibarra [SIAM J. Comput. 18 (1989), 1263--1282], and Hing Leung [SIAM J. Comput. 27 (1998), 1073--1082].
关键词：Communication complexity, descriptional complexity, finite automata, limited ambigiuty, nondeterminism