×

Magic numbers for symmetric difference NFAs. (English) Zbl 1090.68065

Summary: K. Iwama, A. Matsuura and M. Paterson [Theor. Comput. Sci. 301, 451–462 (2003; Zbl 1022.68067)] showed that there exists an \(n\)-state binary nondeterministic finite automaton such that its equivalent minimal deterministic finite automaton has exactly \(2^n-\alpha\) states, for all \(n\geq 7\) and \(5\leq\alpha\leq 2n-2\), subject to certain coprimality conditions. We investigate the same question for both unary and binary symmetric difference nondeterministic finite automata. In the binary case, we show that for any \(n\geq 4\) there is an \(n\)-state symmetric difference nondeterministic finite automaton for which the equivalent minimal deterministic finite automaton has \(2^{n-1}+ 2^{k-1}-1\) states, for \(2<k\leq n-1\). In the unary case, we consider a large practical subclass of unary symmetric difference nondeterministic finite automata: for all \(n\geq 2\), we argue that there are many values of \(\alpha\) such that there is no \(n\)-state unary symmetric difference nondeterministic finite automaton with an equivalent minimal deterministic finite automaton with \(2^n-\alpha\) states, where \(0< \alpha<2^{n-1}\). For each \(n\geq 2\), we quantify such values of \(\alpha\) precisely.

MSC:

68Q45 Formal languages and automata
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q19 Descriptive complexity and finite models

Keywords:

succinctness

Citations:

Zbl 1022.68067
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chaudhuri P. P., Additive Cellular Automata Theory and Applications 1 (1997) · Zbl 0944.68133
[2] Domaratzki M., Journal of Automata, Languages and Combinatorics 7 pp 469– · Zbl 1101.68650
[3] Dornhoff L. L., Applied Modern Algebra (1977) · Zbl 0408.00001
[4] Golomb S. W., Shift Register Sequences (1967)
[5] DOI: 10.1016/S0304-3975(00)00029-3 · Zbl 0939.68068 · doi:10.1016/S0304-3975(00)00029-3
[6] DOI: 10.1016/S0304-3975(02)00891-5 · Zbl 1022.68067 · doi:10.1016/S0304-3975(02)00891-5
[7] Sipser M., Introduction to the Theory of Computation (1997) · Zbl 1169.68300
[8] Stone H., Discrete Mathematical Structures (1973) · Zbl 0293.00002
[9] DOI: 10.1016/j.tcs.2004.07.012 · Zbl 1071.68057 · doi:10.1016/j.tcs.2004.07.012
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.