Model completeness of an algebra of languages

Author:
David Haussler

Journal:
Proc. Amer. Math. Soc. **83** (1981), 371-374

MSC:
Primary 03C60; Secondary 03B25, 03C35, 03C65, 68D30

DOI:
https://doi.org/10.1090/S0002-9939-1981-0624934-6

MathSciNet review:
624934

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: An algebra of languages over a finite alphabet is defined with operations and and its first order theory is shown to be model complete. A characterization of the regular languages as unique solutions of sets of equations in is given and it is shown that the subalgebra where is the set of regular languages is a prime model for the theory of . We show also that the theory of is decidable.

**[1]**J. H. Conway,*Regular algebra and finite machines*, Chapman & Hall, London, 1971.**[2]**J. E. Hopcroft and J. D. Ullman,*Introduction to automata theory, languages and computation*, Addison-Wesley, Reading, Mass., 1979. MR**645539 (83j:68002)****[3]**J. Mycielski and P. Perlmutter,*Model completeness of some metric completions of absolutely free algebras*, Algebra Universalis**12**(1981) (to appear). MR**608657 (82k:03037)****[4]**M. O. Rabin,*Decidability of second-order theories and automata on infinite trees*, Trans. Amer. Math. Soc.**141**(1969), 1-35. MR**0246760 (40:30)**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
03C60,
03B25,
03C35,
03C65,
68D30

Retrieve articles in all journals with MSC: 03C60, 03B25, 03C35, 03C65, 68D30

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1981-0624934-6

Article copyright:
© Copyright 1981
American Mathematical Society