Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 

 

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 $ \left\langle {\mathcal{L},f,g} \right\rangle $ of languages over a finite alphabet $ \Sigma = \{ {a_1}, \ldots ,{a_n}\} $ is defined with operations $ f({L_1}, \ldots ,{L_n}) = {a_1}{L_1} \cup \cdots \cup {a_n}{L_n} \cup \{ \lambda \} $ and $ g({L_1}, \ldots ,{L_n}) = {a_1}{L_1} \cup \cdots \cup {a_n}{L_n}$ 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 $ \left\langle {\mathcal{L},f,g} \right\rangle $ is given and it is shown that the subalgebra $ \left\langle {\mathcal{R},f,g} \right\rangle $ where $ \mathcal{R}$ is the set of regular languages is a prime model for the theory of $ \left\langle {\mathcal{L},f,g} \right\rangle $. We show also that the theory of $ \left\langle {\mathcal{L},f,g} \right\rangle $ is decidable.


References [Enhancements On Off] (What's this?)


Similar Articles

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