×

Locally testable languages. (English) Zbl 0242.68038


MSC:

68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arbib, M., (Theories of Abstract Automata (1969), Prentice-Hall: Prentice-Hall New Jersey) · Zbl 0193.32801
[2] (Arbib, M. A., Algebraic Theory of Machines, Languages and Semigroups (1968), Academic Press: Academic Press New York) · Zbl 0181.01501
[3] Brzozowski, J. A., Canonical regular expressions and minimal state-graphs for definite events, (Proc. Symp. on Math. Theory of Automata (1962), Polytechnic Institute of Brooklyn: Polytechnic Institute of Brooklyn Brooklyn, New York), 529-561 · Zbl 0116.33605
[4] Clifford, A. H.; Preston, G. B., (“The Algebraic Theory of Semigroups,” Vol. 1, Math. Surveys, 7 (1962), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI)
[5] Ginzburg, A., About some properties of definite, reverse-definite and related automata, IEEE Trans. Electronic Computers EC, 15, 806-810 (1966) · Zbl 0156.01904
[6] Krohn, K.; Mateosian, R.; Rhodes, J., Methods of the algebraic theory of machines I. Decomposition theorem for generalized machines; properties preserved under series and parallel composition of machines, J. Comput. System Sci., 1, 55-85 (1967) · Zbl 0207.31502
[7] Krohn, K.; Rhodes, J.; Tilson, B., The prime decomposition theorem of the algebraic theory of machines, (Arbib, M. A., Chapter 5 of “Algebraic Theory of Machines, Languages and Semigroups” (1968), Academic Press: Academic Press New York) · Zbl 0148.01002
[8] Krohn, K.; Rhodes, J.; Tilson, B., Homomorphisms and semi-local theory, (Arbib, M. A., Algebraic Theory of Machines, Languages and Semigroups (1968), Academic Press: Academic Press New York), 191-231
[9] McNaughton, R.; Papert, S., The syntactic monoid of a regular event, (Arbib, M. A., Algebraic Theory of Machines, Languages and Semigroups (1968), Academic Press: Academic Press New York), 297-312
[10] McNaughton, R.; Papert, S., (Counter-Free Automata (1971), MIT Press) · Zbl 0232.94024
[11] McNaughton, R.; Zalcstein, Y., Abstract 71T-C16, Notices Amer. Math. Soc. (June 1971)
[12] Perles, M.; Rabin, M. O.; Shamir, E., The theory of definite automata, IEEE Trans. Electronic Computers EC, 12, 233-243 (1963) · Zbl 0158.01002
[13] D. PerrinC.R. Seminaire Schützenberger; D. PerrinC.R. Seminaire Schützenberger
[14] Rhodes, J.; Tilson, B., Local structure theorems for finite semigroups, (Arbib, M. A., Algebraic Theory of Machines, Languages and Semigroups (1968), Academic Press: Academic Press New York), 147-189
[15] Schützenberger, M. P., On finite monoids having only trivial subgroups, Information and Control, 8, 190-194 (1965) · Zbl 0131.02001
[16] Chomsky, N.; Schützenberger, M. P., The algebraic theory of context-free languages, (Braffort, P.; Hirschberg, D., Computer Programming and Formal Systems (1963), North Holland) · Zbl 0148.00804
[17] Steinby, M., On definite automata and related systems, Ann. Acad. Sci. Fenn. Ser. AI, 444 (1969) · Zbl 0253.94030
[18] Stiffler, P., Extensions of the Fundamental Theorem of Finite Semigroups, (Ph.D. thesis (1970), Department of Mathematics, University of California: Department of Mathematics, University of California Berkeley)
[19] Thatcher, J., Generalized sequential machine maps, J. Comput. System Sci., 4, 339-367 (1970) · Zbl 0198.03303
[20] Zalcstein, Y., Locally Testable Events and Semigroups, (Technical Report (March 1971), Department of Computer Science, Carnegie-Mellon University) · Zbl 0273.20049
[21] Zalcstein, Y., Remarks on automata and semigroups (May, 1971), Unpublished manuscript
[22] Y. Zalcstein; Y. Zalcstein · Zbl 0273.20049
[23] B. TilsonSemigroup Forum; B. TilsonSemigroup Forum · Zbl 0226.20060
[24] Brzozowski, J. A.; Simon, Imre, (“Characterizations of Locally Testable Events,” Technical Report (August, 1971), University of Waterloo) · Zbl 0255.94032
[25] R. McNaughton; R. McNaughton · Zbl 0287.02022
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.