zbMATH — the first resource for mathematics

Pairs of complementary unary languages with “balanced” nondeterministic automata. (English) Zbl 1236.68168
Summary: For each sufficiently large \(n\), there exists a unary regular language \(L\) such that both \(L\) and its complement \(L ^{c}\) are accepted by unambiguous nondeterministic automata with at most \(n\) states, while the smallest deterministic automata for these two languages still require a superpolynomial number of states, at least \(e^{\Omega(\root 3 \of {n\cdot\ln^{2}n})}\). Actually, \(L\) and \(L ^{c}\) are “balanced” not only in the number of states but, moreover, they are accepted by nondeterministic machines sharing the same transition graph, differing only in the distribution of their final states. As a consequence, the gap between the sizes of unary unambiguous self-verifying automata and deterministic automata is also superpolynomial.

68Q45 Formal languages and automata
Full Text: DOI
[1] Anselmo, M., Madonia, M.: Some results on the structure of unary unambiguous automata. Adv. Appl. Math. (2010). doi: 10.1016/j.aam.2010.05.003 · Zbl 1223.68062
[2] Chrobak, M.: Finite automata and unary languages. Theor. Comput. Sci. 47, 149–158 (1986). Corrigendum: ibid. 302, 497–498 (2003) · Zbl 0638.68096 · doi:10.1016/0304-3975(86)90142-8
[3] Ďuriš, P., Hromkovič, J., Rolim, J., Schnitger, G.: Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations. In: Proceedings of Symposium on Theoretical Aspects of Computer Science 1997. LNCS, vol. 1200, pp. 117–128. Springer, Berlin (1997)
[4] Geffert, V.: Magic numbers in the state hierarchy of finite automata. Inf. Comput. 205, 1652–1670 (2007) · Zbl 1130.68069 · doi:10.1016/j.ic.2007.07.001
[5] Grantham, J.: The largest prime dividing the maximal order of an element of S n . Math. Comput. 64, 407–410 (1995) · Zbl 0824.11059
[6] Hromkovič, J., Schnitger, G.: On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. Inf. Comput. 169, 284–296 (2001) · Zbl 1007.68065 · doi:10.1006/inco.2001.3040
[7] Jiang, T., McDowell, E., Ravikumar, B.: The structure and complexity of minimal nfa’s over a unary alphabet. Int. J. Found. Comput. Sci. 2, 163–182 (1991) · Zbl 0746.68040 · doi:10.1142/S012905419100011X
[8] Jirásková, G., Pighizzini, G.: Converting self-verifying automata into deterministic automata. In: Proceedings of Language and Automata Theory and Applications 2009. LNCS, vol. 5457, pp. 458–468. Springer, Berlin (2009) · Zbl 1234.68214
[9] Landau, E.: Über die Maximalordnung der Permutation gegebenen Grades. Arch. Math. Phys. 3, 92–103 (1903) · JFM 34.0233.02
[10] Landau, E.: Handbuch der Lehre von der Verteilung der Primzahlen I. Teubner, Leipzig/Berlin (1909) · JFM 40.0232.08
[11] Ljubič, Ju.I.: Bounds for the optimal determinization of nondeterministic autonomous automata. Sib. Mat. Zh. V/2, 337–355 (1964) (in Russian)
[12] Lupanov, O.B.: A comparison of two types of finite automata. Probl. Kibern. 9, 321–326 (1963) (in Russian). German translation: Über den Vergleich zweier Typen endlicher Quellen. Probleme der Kybernetik 6, 329–335 (1966)
[13] Mandl, R.: Precise bounds associated with the subset construction of various classes of nondeterministic finite automata. In: Proceedings of 7th Princeton Conference of Information and System Sciences, pp. 263–267 (1973)
[14] Mera, F., Pighizzini, G.: Complementing unary nondeterministic automata. Theor. Comput. Sci. 330, 349–360 (2005) · Zbl 1078.68091 · doi:10.1016/j.tcs.2004.04.015
[15] Mereghetti, C., Pighizzini, G.: Optimal simulations between unary automata. SIAM J. Comput. 30, 1976–1992 (2001) · Zbl 0980.68048 · doi:10.1137/S009753979935431X
[16] Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: Proceedings of 12th Annual IEEE Symposium on Switching and Automata Theory, pp. 188–191 (1971)
[17] Miller, W.: The maximum order of an element of a finite symmetric group. Am. Math. Mon. 94, 497–506 (1987) · Zbl 1191.11027 · doi:10.2307/2322839
[18] 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. C-20(10), 1211–1214 (1971) · Zbl 0229.94033 · doi:10.1109/T-C.1971.223108
[19] Nicolas, J.-L.: Sur l’ordre maximum d’un élément dans le groupe S n des permutations. Acta Arith. 14, 315–332 (1968) · Zbl 0179.34804
[20] Okhotin, A.: Unambiguous finite automata over a unary alphabet. In: Proceedings of Mathematical Foundations of Computer Science 2010. LNCS, vol. 6281, pp. 556–567. Springer, Berlin (2010) · Zbl 1287.68098
[21] Rabin, M., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3, 114–125 (1959) · Zbl 0158.25404 · doi:10.1147/rd.32.0114
[22] Ramanujan, S.: A proof of Bertrand’s postulate. J. Indian Math. Soc. 11, 181–182 (1919)
[23] Ravikumar, B., Ibarra, O.: Relating the type of ambiguity of finite automata to the succinctness of their representation. SIAM J. Comput. 18, 1263–1282 (1989) · Zbl 0692.68049 · doi:10.1137/0218083
[24] Szalay, M.: On the maximal order in S n and $S_{n}\^{*}$ . Acta Arith. 37, 321–331 (1980) · Zbl 0443.10029
[25] To, A.W.: Unary finite automata vs. arithmetic progressions. Inf. Process. Lett. 109, 1010–1014 (2009) · Zbl 1202.68241 · doi:10.1016/j.ipl.2009.06.005
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.