Algebraic decision procedures for local testability. (English) Zbl 0287.02022


03D05 Automata and formal grammars in connection with logical questions
68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
Full Text: DOI


[1] J. A. Brzozowski andI. Simon, Characterizations of locally testable events,Discrete Mathematics 4 (1973), 243–271. · Zbl 0255.94032 · doi:10.1016/S0012-365X(73)80005-6
[2] N. Chomsky andM. P. Schützenberger, The algebraic theory of context-free languages, inComputer Programming and Formal Systems (P. Braffort and D. Hirschberg, editors), North Holland, Amsterdam, 1963, pp. 118–161.
[3] L. S. Levy andM. Freeman, Finitely generated events, unpublished paper, 1970.
[4] R. McNaughton andS. Papert,Counter-free Automata, M.I.T. Press, Cambridge, Mass., 1971.
[5] Yu. T. Medvedev, On the class of events representable in a finite automaton (translated from the Russian), inSequential Machines–Selected Papers (E. F. Moore, ed.), Addison-Wesley, 1964, pp. 215–227.
[6] M. Perles, M. O. Rabin andE. Shamir, The theory of definite automata,Trans. IEEE EC-12 (1963), 233–243. · Zbl 0158.01002
[7] F. P. Ramsey, On a problem of formal logic,Proc. London Math. Soc.,30 (Ser. 2, 1928), Part 4, 338–384. Reprinted in a paperback,The Foundations of Mathematics and other Logical Essays, by F. P. Ramsey, Littlefield, Adams and Co., Patterson, N. J., 1960. (This book was first printed by Routledge and Kegan Paul, London, 1931).
[8] Y. Zalcstein, Locally testable languages,J. Computer Systems Science 6 (1972), 151–167. · Zbl 0242.68038 · doi:10.1016/S0022-0000(72)80020-5
[9] Y. Zalcstein, Locally testable semigroups,Semigroup Forum 5 (1973), 216–227. · Zbl 0273.20049 · doi:10.1007/BF02572893
[10] Y. Zalcstein, Syntactic semigroups of some classes of star-free languages,Proc. International Symposium on Theory of Automata, Languages and Programming (IRIA, Paris), North Holland Publishing Company, Amsterdam, 1972, pp. 135–144.
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.