Concatenation of regular languages and descriptional complexity

DOI10.1007/s00224-011-9318-7zbMath1222.68110OpenAlexW1972592804MaRDI QIDQ639851

Galina Jirásková

Publication date: 11 October 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-011-9318-7

zbMATH Keywords

regular languagesstate complexityconcatenation

Mathematics Subject Classification ID

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

Related Items

The Complexity of Languages Resulting from the Concatenation Operation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• 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
• A family of NFAs which need 2\(^{n}-\alpha\) deterministic states
• Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
• State complexity of some operations on binary regular languages
• Magic numbers in the state hierarchy of finite automata
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• On the State Complexity of Operations on Two-Way Finite Automata
• Magic Numbers and Ternary Alphabet
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• MAGIC NUMBERS FOR SYMMETRIC DIFFERENCE NFAS