×

Weak second-order arithmetic and finite automata. (English) Zbl 0103.24705


MSC:

03D05 Automata and formal grammars in connection with logical questions
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Hopcroft J E, Ullman J D. Introduction to Automata Theory, Languages and Computation. New York: Addison-Wesley, 1979 · Zbl 0426.68001
[2] Büchi J R. Weak second-order arithmetic and finite automata. Zeitschrifit für Mathematische Logik and Grundlagen der Mathematik, 1960, 6: 66-92 · Zbl 0103.24705
[3] Elgot C C. Decision problems of finite automata design and related arithmetics. Trans Am Math Society, 1961, 98: 21-52 · Zbl 0111.01102
[4] Schützenberger M O. On finite monoids having only trivial subgroups. Inf Control, 1965, 8: 190-194 · Zbl 0131.02001
[5] McNaughton R, Papert S. Counter-Free Automata. Cambridge: MIT Press, 1971
[6] Eilengerb S. Automata, Languages and Machines, vol. A, vol B. New York: Academic Press, 1974
[7] Droste M, Gastin P. Weighted automata and weighted logics. Theor Comput Sci, 2007, 380: 69-86 · Zbl 1118.68076
[8] Mcmillan K. Symbolic Model Checking. Dordrecht: Kluwer Academic Publisher, 1993 · Zbl 0784.68004
[9] Nielsen M A, Chuang I L. Quantum Computation and Quantum Information. Cambridge: Cambridge University, 2000 · Zbl 1049.81015
[10] Ying M S. Automata theory based on quantum logic (I). Int J Theor Phys, 2000, 39: 981-991
[11] Ying M S. Automata theory based on quantum logic (II). Int J Theor Phys, 2000, 39: 2545-2557 · Zbl 1047.81007
[12] Ying M S. A theory of computation based on quantum logic (I). Theor Comput Sci, 2005, 344: 134-207 · Zbl 1079.68035
[13] Qiu D W. Automata theory based on quantum logic: reversibilities and pushdown automata. Theor Comput Sci, 2007, 386: 38-56 · Zbl 1137.68036
[14] Qiu D W. Notes on automata theory based on quantum logic. Sci China Ser F-Inf Sci, 2007, 50: 154-169 · Zbl 1121.68068
[15] Kalmbach G. Orthomodular Lattices. London: Academic Press, 1983 · Zbl 0512.06011
[16] Li Y M, Li Z H. Free semilattices and strongly free semilattices generated by partially ordered sets. Northeast Math J, 1993, 9: 359-366 · Zbl 0805.06004
[17] Rabin M, Scott D. Finite automata and their decision problems. IBM J Research Develop, 1959, 3: 114-125 · Zbl 0158.25404
[18] Li Y M, Pedrycz W. Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids. Fuzzy Sets Syst, 2005, 156: 68-92 · Zbl 1083.68059
[19] Li Y M. Approximation and universality of fuzzy Turing machines. Sci China Ser F-Inf Sci, 2008, 51: 1445-1465 · Zbl 1151.68011
[20] Khoussainov B, Nerode A. Automata Theory and its Applications. Boston: Birkäuser, 2001 · Zbl 1083.68058
[21] Thomas W. Languages,
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.