Characterizations of locally testable events. (English) Zbl 0255.94032


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


[1] Brzozowski, J. A., Canonical regular expressions and minimal state graphs for definite events, (Proc. of the Symp. of Math. (1962), Theory of Automata, Polytechnic Institute of Brooklyn: Theory of Automata, Polytechnic Institute of Brooklyn New York), 529-561 · Zbl 0116.33605
[2] Cohen, R. S.; Brzozowski, J. A., Dot depth of star-free events, J. Comput. System Sci., 5, 1-16 (1971) · Zbl 0217.29602
[3] Ginzburg, A., Algebraic theory of automata (1968), Academic Press: Academic Press Brooklyn, New York · Zbl 0195.02501
[4] Ginzburg, A., About some properties of definite, reverse-definite and related automata, IEEE Trans. on Electr. Comput., EC-15, 806-810 (1966) · Zbl 0156.01904
[5] Kleene, S. C., Representation of events in nerve nets and finite automata, (Shannon, C. E.; McCarthy, J., Automata Studies, 34 (1954), Princeton University Press: Princeton University Press New York), 3-41 · Zbl 0061.01003
[6] McNaughton, R.; Papert, S., Counter-free automata (1971), M.I.T. Press: M.I.T. Press Princeton, N.J. · Zbl 0232.94024
[7] McNaughton, R.; Zalcstein, Y., Abstract 71T-C16, Notices Am. Math. Soc., 18, 657 (1971)
[8] Perles, M.; Rabin, O.; Shamir, E., The theory of definite automata, IEEE Trans. Electr. Comput., EC-12, 233-243 (1963) · Zbl 0158.01002
[9] Zalcstein, Y., Locally testable languages, J. Comput. System Sci., 6, 151-167 (1972) · Zbl 0242.68038
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.