zbMATH — the first resource for mathematics

Complementing unary nondeterministic automata. (English) Zbl 1078.68091
Summary: We compare the nondeterministic state complexity of unary regular languages and that of their complements: if a unary language \(\mathcal L\) has a succinct nondeterministic finite automaton, then nondeterminism is useless in order to recognize its complement, namely, the smallest nondeterministic automaton accepting the complement of \(\mathcal L\) has as many states as the minimum deterministic automaton accepting it. The same property does not hold in the case of automata and languages defined over larger alphabets. We also show the existence of infinitely many unary regular languages for which nondeterminism is useless in their recognition and in the recognition of their complements.

68Q45 Formal languages and automata
Full Text: DOI
[1] Birget, J.C., Partial orders on words, minimal elements of regular languages, and state complexity, Theoret. comput. sci., 119, 267-291, (1993), Erratum available at \(\sim\) · Zbl 0786.68071
[2] Chrobak, M., Finite automata and unary languages, Theoret. comput. sci., 47, 149-158, (1986), Erratum Theoret. Comput. Sci. 302 (2003) 497-498 · Zbl 0638.68096
[3] K. Ellul, Descriptional complexity measures of regular languages, M. Math. Thesis, University of Waterloo, 2002.
[4] Goldstine, J.; Kappes, M.; Kintala, C.; Leung, H.; Malcher, A.; Wotschke, D., Descriptional complexity of machines with limited resources, J. univ. comput. sci., 8, 2, 193-234, (2002) · Zbl 1258.68058
[5] Hardy, G.H.; Wright, E.M., An introduction to the theory of numbers, (1979), Oxford Science Publications Oxford · Zbl 0423.10001
[6] M. Holzer, M. Kutrib, Unary language operations and their nondeterministic state complexity, Developments in Language Theory, DLT 2002, Lecture Notes in Computer Science, vol. 2459, 2003, pp. 162-172. · Zbl 1015.68118
[7] Holzer, M.; Kutrib, M., Nondeterministic descriptional complexity of regular languages, Internat. J. found. comput. sci., 14, 1087-1102, (2003) · Zbl 1101.68657
[8] Hopcroft, J.E.; Motwani, R.; Ullman, J.D., Introduction to automata theory, languages, and computation, (2001), Addison-Wesley Reading, MA · Zbl 0980.68066
[9] J. Hromkovič, Descriptional complexity of regular languages (concepts and open problems), Proc. Descriptional Complexity of Automata, Grammars and Related Structures, Vienna, 2001, Report 16-2001, Otto-Von-Guericke-Universität Magdeburg, pp. 11-13.
[10] Jiang, T.; McDowell, E.; Ravikumar, B., The structure and complexity of minimal Nfa’s over a unary alphabet, Internat. J. found. comput. sci., 2, 163-182, (1991) · Zbl 0746.68040
[11] G. Jirásková, State complexity of some operations on regular languages, Proc. Descriptional Complexity of Formal Systems 2003, MTA SZTAKI, Budapest, pp. 114-125.
[12] Landau, E., Über die maximalordnung der permutationen gegebenen grades, Arch. math. phys., 3, 92-103, (1903) · JFM 34.0233.02
[13] Landau, E., Handbuch der lehre von der verteilung der primzahlen I, (1909), Teubner Leipzig, Berlin · JFM 40.0232.08
[14] Leiss, E., Succinct representation of regular languages by Boolean automata, Theoret. comput. sci., 13, 323-330, (1981) · Zbl 0458.68017
[15] Mereghetti, C.; Pighizzini, G., Two-way automata simulations and unary languages, J. automat. languages combin., 5, 287-300, (2000) · Zbl 0965.68043
[16] Mereghetti, C.; Pighizzini, G., Optimal simulations between unary automata, SIAM J. comput., 30, 1976-1992, (2001) · Zbl 0980.68048
[17] Meyer, A.; Fischer, M., Economy of description by automata, grammars, and formal systems, (), 188-191
[18] Moore, F., On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic and two-way finite automata by deterministic automata, IEEE trans. comput., C-20, 1211-1219, (1971) · Zbl 0229.94033
[19] C. Nicaud, Average state complexity of operations on unary automata, Proc. MFCS’99, Lecture Notes in Computer Science, vol. 1672, 1999, pp. 231-240. · Zbl 0955.68068
[20] Pighizzini, G.; Shallit, J.O., Unary languages operations, state complexity and Jacobsthal’s function, Internat. J. found. comput. sci., 13, 145-159, (2002) · Zbl 1066.68072
[21] Rabin, M.O.; Scott, D., Finite automata and their decision problems, IBM J. res. develop., 3, 198-200, (1959), also in: E.F. Moore (Ed.), Sequential Machines: Selected Papers, Addison-Wesley, Reading, MA, 1964, pp. 63-91 · Zbl 0158.25404
[22] Szalay, M., On the maximal order in \(S_n\) and \(S_n^*\), Acta arith., 37, 321-331, (1980) · Zbl 0443.10029
[23] Yu, S., A renaissance of automata theory?, EATCS bull., 72, 270-272, (2000)
[24] Yu, S., State complexity of regular languages, J. automat. languages combin., 6, 221-234, (2001) · Zbl 0978.68087
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.