On the boundary of regular languages

DOI10.1016/J.TCS.2015.01.022MaRDI QIDQ2344745zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 18 May 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.01.022

zbMATH Keywords

boundarydeterministic finite automatonregular languagestate complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

This paper considers the computation of the boundary of a regular language, defined as the intersection of the Kleene star of this language with the Kleene star of its complement. The precise state complexity of the boundary of a regular language is found. The upper bound is obtained by counting unreachable states in the automaton produced using standard constructions for Kleene star and intersection, and it is proved that this upper bound can be reached by automata over a five-letter alphabet. A precise bound in the case of a four-letter alphabet and asymptotic bounds for two- and three-letter alphabets are also provided.

Recommendations

• On the boundary of regular languages
• The boundary of prefix-free languages
• Boundary sets of regular and context-free languages
• Boundary sets of regular and context-free languages
• State complexity of boundary of prefix-free regular languages

Cites work

• Closures in formal languages and Kuratowski's theorem
• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• State complexity of combined operations
• The Kuratowski Closure-Complement Problem
• The state complexities of some basic operations on regular languages
• The state complexity of star-complement-star

Cited in

(17)

• An optimal lower bound for nonregular languages
• Regular languages defined by generalized first-order formulas with a bounded number of bound variables
• Some results of Zoltán Ésik on regular languages
• On decidability of theories of regular languages
• Kuratowski algebras generated by prefix-free languages
• The boundary of prefix-free languages
• The topological structure of adherences of regular languages
• scientific article; zbMATH DE number 611232 (Why is no real title available?)
• scientific article; zbMATH DE number 1944129 (Why is no real title available?)
• scientific article; zbMATH DE number 871439 (Why is no real title available?)
• On the boundary of regular languages
• scientific article; zbMATH DE number 5218131 (Why is no real title available?)
• On Notions of Regularity for Data Languages
• Developments in Language Theory
• Boundary sets of regular and context-free languages
• The boundary operation on some subclasses of convex regular languages
• Boundary sets of regular and context-free languages

This page was built for publication: On the boundary of regular languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2344745)