Photo by nevenkrcmarek from unsplash
This paper is dedicated to studying model-theoretic and complexity properties of the theory of regular languages with the Kleene star operation. We construct a ‘‘natural’’ infinite set of axioms for… Click to show full abstract
This paper is dedicated to studying model-theoretic and complexity properties of the theory of regular languages with the Kleene star operation. We construct a ‘‘natural’’ infinite set of axioms for this theory, and we prove that it is not finitely axiomatizable. We establish that this theory is countably categorical, but it is not categorical in any uncountable cardinality. Also, we find the exact amount of non-isomorphic models of given cardinality. Finally, we prove that the theory of regular languages with the Kleene star is PSPACE-complete.
Journal Title: Lobachevskii Journal of Mathematics
Year Published: 2020
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!