Abstract
The degree of nondeterminism of a finite automaton can be measured by means of its ambiguity function. In many instances, whenever automata are allowed to be (substantially) less ambiguous, it is known that the number of states needed to recognize at least some languages increases exponentially. However, when comparing constantly ambiguous automata with polynomially ambiguous ones, the question whether there are languages such that the inferior class of automata requires exponentially many states more than the superior class to recognize them is still an open problem. The purpose of this paper is to suggest a family of languages that seems apt for a proof of this (conjectured) gap. As a byproduct, we derive a new variant of the proof of the existence of a superpolynomial gap between polynomial and fixed-constant ambiguity. Although our candidate languages are defined over a huge alphabet, we show how to overcome this drawback.
This work was supported by SNF grant 200021-107327/1.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata and Language Theory. Addison-Wesley, Reading (2000)
Hromkovič, J.: Communication Complexity and Parallel Computing. Springer, Heidelberg (1997)
Hromkovi č, J., Karhumäki, J., Klauck, H., Seibert, S., Schnitger, G.: Measures on Nondeterminism in Finite Automata. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 199–210. Springer, Heidelberg (2000)
Kupke, J.: Limiting the Ambiguity of Non-Deterministic Finite Automata. Diploma Thesis, RWTH Aachen (2002), Available online at: http://www-i1.informatik.rwth-aachen.de/~joachimk/ltaondfa.ps
Kupke, J.: On Separating Constant from Polynomial Ambiguity of Finite Automata, http://www.ite.ethz.ch/people/jkupke/publications/oscfpaofa.ps
Gramlich, G., Schnitger, G.: Minimizing NFAs and Regular Expressions. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 399–411. Springer, Heidelberg (2005)
Leung, H.: Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata. SIAM J. Comp. 27, 1073–1082 (1998)
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)
Ravikumar, B., Ibarra, O.: Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation. SIAM J. Comp. 18, 1263–1282 (1989)
Sipser, M.: Lower Bounds on the Size of Sweeping Automata. J. Comp. and Sys. Sci. 21(2), 195–202 (1980)
Weber, A., Seidl, H.: On the Ambiguity of Finite Automata. In: Wiedermann, J., Gruska, J., Rovan, B. (eds.) MFCS 1986. LNCS, vol. 233, pp. 620–629. Springer, Heidelberg (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kupke, J. (2006). On Separating Constant from Polynomial Ambiguity of Finite Automata. In: Wiedermann, J., Tel, G., Pokorný, J., Bieliková, M., Štuller, J. (eds) SOFSEM 2006: Theory and Practice of Computer Science. SOFSEM 2006. Lecture Notes in Computer Science, vol 3831. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11611257_36
Download citation
DOI: https://doi.org/10.1007/11611257_36
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-31198-0
Online ISBN: 978-3-540-32217-7
eBook Packages: Computer ScienceComputer Science (R0)