Hromkovič, Juraj; Seibert, Sebastian; Karhumäki, Juhani; Klauck, Hartmut; Schnitger, Georg Communication complexity method for measuring nondeterminism in finite automata. (English) Zbl 1009.68067 Inf. Comput. 172, No. 2, 202-217 (2002). Summary: 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 nfa’s with bounded unambiguity. Applying this fact, the proofs of several results about nfa’s with limited ambiguity can be simplified and presented in a uniform way.2. There is a family of languages \(\text{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 B. Ravikumar and O. H. Ibarra [SIAM J. Comput. 18, 1263-1282 (1989; Zbl 0692.68049)] and H. Leung [SIAM J. Comput. 27, 1073-1082 (1998; Zbl 0911.68144)]. Cited in 37 Documents MSC: 68Q45 Formal languages and automata 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) Citations:Zbl 0692.68049; Zbl 0911.68144 PDFBibTeX XMLCite \textit{J. Hromkovič} et al., Inf. Comput. 172, No. 2, 202--217 (2002; Zbl 1009.68067) Full Text: DOI References: [1] Rabin, M.; Scott, D., Finite automata and their decision problems, IBM J. Res. Devel., 3, 114-125 (1959) · Zbl 0158.25404 [2] Hromkovič, J.; Seibert, S.; Wilke, T., Translating regular expressions into small ϵ-free nondeterministic finite automata, Proc. STACS’97 (1997), Springer-Verlag: Springer-Verlag Berlin, p. 55-66 · Zbl 1498.68138 [3] Sipser, M., Lower bounds on the size of sweeping automata, J. Comput. System Sci., 21, 195-202 (1981) · Zbl 0445.68064 [4] Micali, S., Two-way deterministic finite automata are exponentially more succinct than sweeping automata, Inform. Process. Lett., 12, 103-105 (1981) · Zbl 0471.68039 [5] Hromkovič, J.; Schnitger, G., On the power of Las Vegas II. Two-way finite automata, Proc. ICALP’99 (1999), Springer-Verlag: Springer-Verlag Berlin, p. 433-443 · Zbl 0939.68071 [6] Hromkovič, J., and Schnitger, G.Theoret. Comput. Sci.262, 1-24.; Hromkovič, J., and Schnitger, G.Theoret. Comput. Sci.262, 1-24. [7] Meyer, A. R.; Fischer, M. J., Economy of description by automata, grammars and formal systems, Proc. 12th Annual Symp. on Switching and Automata Theory (1971), p. 188-191 [8] Moore, F., On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic and two-way finite automata, IEEE Trans. Comput., 20, 1211-1214 (1971) · Zbl 0229.94033 [9] Schmidt, E., Succinctness of Descriptions of Context-Free, Regular and Finite Languages (1978), Cornell University: Cornell University Ithaca [10] Hromkovič, J., Communication Complexity and Parallel Computing (1997), Springer-Verlag: Springer-Verlag Berlin/New York · Zbl 0873.68098 [11] Stearns, R.; Hunt, H., On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata, SIAM J. Comput., 14, 598-611 (1985) · Zbl 0577.68074 [12] Ravimkumar, B.; Ibarra, O., Relating the type of ambiguity of finite automata to the succinctness of their representation, SIAM J. Comput., 19, 1263-1282 (1989) · Zbl 0692.68049 [13] Leung, H., Separating exponentially amgigous finite automata from polynomially ambigous finite automata, SIAM J. Comput., 27, 1073-1082 (1998) · Zbl 0911.68144 [14] Hromkovič, J.; Karhumäki, J.; Klauck, H.; Seibert, S.; Schnitger, G., Measures of nondeterminism in finite automata, Proc. ICALP ’00 (2000), Springer-Verlag: Springer-Verlag Berlin, p. 199-210 · Zbl 0973.68114 [15] Yao, A., Some complexity questions related to distributed computing, Proc. 11th ACM STOC (1979), Assoc. Comput. Mach: Assoc. Comput. Mach New York, p. 209-213 [16] Abelson, H., Lower bounds on information transfer in distributed computations, Proc. 19th IEEE FOCS (1978), IEEE Press: IEEE Press New York, p. 151-158 [17] Thompson, C. D., Area-time complexity for VLSI, Proc. 11th ACM STOC (1979), Assoc. Comput. Mach: Assoc. Comput. Mach New York, p. 81-88 [18] Thompson, C. D., A Complexity Theory for VLSI (1980), Carnagie-Mellon UniversityComputer Science Department: Carnagie-Mellon UniversityComputer Science Department Pittsburgh [19] Kushilevitz, E.; Nisan, N., Communication Complexity (1997), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0869.68048 [20] Aho, A. V.; Ullman, J. D.; Yannakakis, M., On notions of informations transfer in VLSI circuits, Proc. 15th ACM STOC (1983), Assoc. Comput. Mach: Assoc. Comput. Mach New York, p. 133-139 [21] Dietzfelbinger, M.; Hromkovič, J.; Schnitger, G., A comparison of two lower bound methods for communication complexity, Theoret. Comput. Sci., 168, 39-51 (1996) · Zbl 0874.68150 [22] Hromkovič, J., Communication protocols: An exemplary study of the power of randomness, (Pardalos, P.; Rajarekaran, S.; Reif, J.; Rolim, J., Handbook of Randomized Computing (2001), Kluwer Academic: Kluwer Academic Dordrecht/Norwell), 533-596 · Zbl 1056.68087 [23] Lovász, L., Communication complexity: A survey, Paths, Flows, and VLSI Layout (1990), Springer-Verlag: Springer-Verlag Berlin/New York · Zbl 0725.68046 [24] Nisan, N.; Wigderson, A., On ranks vs. communication complexity, Combinatorica, 15, 557-565 (1995) · Zbl 0845.68038 [25] Papadimitriou, C.; Sipser, M., Communication complexity, Proc. 14th ACM STOC (1982), Assoc. Comput. Mach: Assoc. Comput. Mach New York, p. 196-200 [26] Karchmer, M.; Saks, M.; Newman, I.; Wigderson, A., Non-deterministic communication complexity with few witnesses, J. Comput. System Sci., 49, 247-257 (1994) · Zbl 0821.68067 [27] Hromkovič, J.; Schnitger, G., Nondeterministic communication with a limited number of advice bits, Proc. 28th ACM STOC (1996), Assoc. Comput. Mach: Assoc. Comput. Mach New York, p. 451-560 · Zbl 0922.68060 [28] Duriš, P.; Hromkovič, J.; Rolim, J. D.P.; Schnitger, G., Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations, Proc. STACS’97 (1997), Springer-Verlag: Springer-Verlag Berlin, p. 117-128 · Zbl 1498.68125 [29] Hromkovič, J., and Schnitger, G., On the power of Las Vegas for one-way communication complexity, OBDD’s, and finite automata, Inform. and Comput.169, 284-296.; Hromkovič, J., and Schnitger, G., On the power of Las Vegas for one-way communication complexity, OBDD’s, and finite automata, Inform. and Comput.169, 284-296. · Zbl 1007.68065 [30] Goldstine, J.; Kintala, C. M.R.; Wotschke, D., On measuring nondeterminism in regular languages, Inform. and Comput., 86, 179-194 (1990) · Zbl 0698.68068 [31] Goldstine, J.; Leung, H.; Wotschke, D., On the relation between ambiguity and nondeterminism in finite automata, Inform. and Comput., 100, 261-270 (1992) · Zbl 0752.68056 [32] Hromkovič, J., Relation between Chomsky hierarchy and communication complexity hierarchy, Acta Math. Univ. Com., 48/49, 311-317 (1986) · Zbl 0631.68068 [33] Eilenberg, S., Automata, Languages and Machines (1974), Academic Press: Academic Press San Diego · Zbl 0317.94045 [34] Jirásková, G., Finite automata and communication protocols, in; Jirásková, G., Finite automata and communication protocols, in [35] Mehlhorn, K.; Schmidt, E., Las Vegas is better than determinism in VLSI and distributed computing, Proc. 14th ACM STOC (1982), Assoc. Comput. Mach: Assoc. Comput. Mach New York, p. 330-337 [36] Yannakakis, M., Expressing combinatorial optimization problems by linear programs, J. Comput. System Sci., 43, 223-228 (1991) [37] Ibarra, O.; Ravikumar, B., On sparseness, ambiguity and other decision problems for acceptors and tranducers, Proc. 3rd STACS ’86 (1986), Springer-Verlag: Springer-Verlag Berlin, p. 171-179 [38] Jurdzinski, M, personal communication.; Jurdzinski, M, personal communication. [39] Klauck, H, On automata with constant ambiguity, manuscript.; Klauck, H, On automata with constant ambiguity, manuscript. · Zbl 0935.68027 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.