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

MathSciNet review:
624934

Full-text PDF Free Access

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]**John E. Hopcroft and Jeffrey D. Ullman,*Introduction to automata theory, languages, and computation*, Addison-Wesley Publishing Co., Reading, Mass., 1979. Addison-Wesley Series in Computer Science. MR**645539****[3]**Jan Mycielski and Paul Perlmutter,*Model completeness of some metric completions of absolutely free algebras*, Algebra Universalis**12**(1981), no. 2, 137–144. MR**608657**, 10.1007/BF02483872**[4]**Michael O. Rabin,*Decidability of second-order theories and automata on infinite trees.*, Trans. Amer. Math. Soc.**141**(1969), 1–35. MR**0246760**, 10.1090/S0002-9947-1969-0246760-1

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