COMPLEXITY IN UNION-FREE REGULAR LANGUAGES

DOI10.1142/S0129054111008933zbMath1252.68148MaRDI 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)

zbMATH Keywords

finite automaton; closure properties; descriptional complexity; one-cycle-free-path automaton; union-free regular language

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q19: Descriptive complexity and finite models

Related Items

State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages, Descriptional Complexity of the Forever Operator, Languages, Decidability, and Complexity, On a structural property in the state complexity of projected regular languages, Nondeterministic complexity in subclasses of convex languages, Nondeterministic complexity of operations on free and convex languages, Nondeterministic Complexity of Operations on Closed and Ideal Languages

Cites Work

• Unnamed Item
• 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