zbMATH — the first resource for mathematics

Locally testable languages. (English) Zbl 0242.68038

68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
Full Text: DOI
[1] Arbib, M., ()
[2] ()
[3] Brzozowski, J.A., Canonical regular expressions and minimal state-graphs for definite events, (), 529-561 · Zbl 0116.33605
[4] Clifford, A.H.; Preston, G.B., ()
[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, () · Zbl 0148.01002
[8] Krohn, K.; Rhodes, J.; Tilson, B., Homomorphisms and semi-local theory, (), 191-231
[9] McNaughton, R.; Papert, S., The syntactic monoid of a regular event, (), 297-312
[10] McNaughton, R.; Papert, S., ()
[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] {\scD. Perrin}, Sur certaines semigroups syntaxique, C.R. Seminaire Schützenberger, to appear.
[14] Rhodes, J.; Tilson, B., Local structure theorems for finite semigroups, (), 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, () · 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, ()
[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, () · Zbl 0273.20049
[21] Zalcstein, Y., Remarks on automata and semigroups, (May, 1971), Unpublished manuscript
[22] {\scY. Zalcstein}, Locally testable semigroups, to appear. · Zbl 0273.20049
[23] {\scB. Tilson}, Decomposition and complexity of finite semigroups, Semigroup Forum, to appear. · Zbl 0226.20060
[24] Brzozowski, J.A.; Simon, Imre, ()
[25] {\scR. McNaughton}, Algebraic decision procedures for local testability, to appear. · 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. 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.