COMPLEXITY IN UNION-FREE REGULAR LANGUAGES

DOI10.1142/S0129054111008933zbMath1252.68148OpenAlexW1980726210MaRDI QIDQ2909101

Galina Jirásková, Tomáš Masopust

Publication date: 29 August 2012

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054111008933

zbMATH Keywords

finite automatonclosure propertiesdescriptional complexityone-cycle-free-path automatonunion-free regular language

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive complexity and finite models (68Q19)

Related Items

Operations on Permutation Automata ⋮ Nondeterministic complexity of operations on free and convex languages ⋮ Nondeterministic operational complexity in subregular languages ⋮ A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity ⋮ Union-Freeness Revisited — Between Deterministic and Nondeterministic Union-Free Languages ⋮ On a structural property in the state complexity of projected regular languages ⋮ Descriptional Complexity of the Forever Operator ⋮ Power, positive closure, and quotients on convex languages ⋮ Nondeterministic Complexity of Operations on Closed and Ideal Languages ⋮ Nondeterministic complexity in subclasses of convex languages ⋮ Languages, Decidability, and Complexity ⋮ State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages ⋮ Closure properties of subregular languages under operations ⋮ Operations on subregular languages and nondeterministic state complexity ⋮ Union-complexities of Kleene plus operation ⋮ Operational union-complexity

Cites Work

• Descriptional and computational complexity of finite automata -- a survey
• On the state complexity of reversals of regular languages
• A lower bound technique for the size of nondeterministic finite automata
• Partial orders on words, minimal elements of regular languages, and state complexity
• The state complexity of \(L^{2}\) and \(L^k\)
• State complexity of power
• State complexity of basic operations on suffix-free regular languages
• Succinct representation of regular languages by Boolean automata
• Intersection and union of regular languages and state complexity
• The state complexities of some basic operations on regular languages
• State complexity of some operations on binary regular languages
• On equations for union-free regular languages
• State complexity of cyclic shift
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• Unnamed Item