×

zbMATH — the first resource for mathematics

Converting self-verifying automata into deterministic automata. (English) Zbl 1234.68214
Dediu, Adrian Horia (ed.) et al., Language and automata theory and applications. Third international conference, LATA 2009, Tarragona, Spain, April 2–8, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-00981-5/pbk). Lecture Notes in Computer Science 5457, 458-468 (2009).
Summary: Self-verifying automata are a special variant of finite automata with a symmetric kind of nondeterminism. In this paper, we study the transformation of self-verifying automata into deterministic automata from a descriptional complexity point of view. The main result is the exact cost, in terms of the number of states, of such a simulation.
For the entire collection see [Zbl 1158.68001].

MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Goldstine, J., Kappes, M., Kintala, C.M.R., Leung, H., Malcher, A., Wotschke, D.: Descriptional complexity of machines with limited resources. J. UCS 8(2), 193–234 (2002) · Zbl 1258.68058
[2] Rabin, M., Scott, D.: Finite automata and their decision problems. IBM J. Res. Develop. 3, 114–125 (1959) · Zbl 0158.25404 · doi:10.1147/rd.32.0114
[3] Lupanov, O.: A comparison of two types of finite automata. Problemy Kibernet 6, 321–326 (1963) (in Russian); German translation: Über den Vergleich zweier Typen endlicher Quellen, Probleme der Kybernetik 6, 329–335 (1966)
[4] Moore, F.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Transactions on Computers C-20(10), 1211–1214 (1971) · Zbl 0229.94033 · doi:10.1109/T-C.1971.223108
[5] Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: Proc. 12th Ann. IEEE Symp. on Switching and Automata Theory, pp. 188–191 (1971) · doi:10.1109/SWAT.1971.11
[6] Ďuriš, P., Hromkovič, J., Rolim, J., Schnitger, G.: Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol. 1200, pp. 117–128. Springer, Heidelberg (1997) · doi:10.1007/BFb0023453
[7] Hromkovič, J., Schnitger, G.: Nondeterministic communication with a limited number of advice bits. SIAM J. Comput. 33(1), 43–68 (2003) · Zbl 1040.68046 · doi:10.1137/S0097539702414622
[8] Hromkovič, J., Schnitger, G.: On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. Information and Computation 169(2), 284–296 (2001) · Zbl 1007.68065 · doi:10.1006/inco.2001.3040
[9] Assent, I., Seibert, S.: An upper bound for transforming self-verifying automata into deterministic ones. Theoretical Informatics and Applications 41(3), 261–265 (2007) · Zbl 1130.68067 · doi:10.1051/ita:2007017
[10] Moon, J., Moser, L.: On cliques in graphs. Israel J. Math. 3, 23–28 (1965) · Zbl 0144.23205 · doi:10.1007/BF02760024
[11] Chrobak, M.: Finite automata and unary languages. Theoretical Computer Science 47, 149–158 (1986); Corrigendum. ibid 302, 497–498 (2003) · Zbl 0638.68096 · doi:10.1016/0304-3975(86)90142-8
[12] Mera, F., Pighizzini, G.: Complementing unary nondeterministic automata. Theoretical Computer Science 330(2), 349–360 (2005) · Zbl 1078.68091 · doi:10.1016/j.tcs.2004.04.015
[13] Holzer, M., Salomaa, K., Yu, S.: On the state complexity of k-entry deterministic finite automata. Journal of Automata, Languages and Combinatorics 6(4), 453–466 (2001) · Zbl 1050.68093
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.