The Complexity of Languages Resulting from the Concatenation Operation

DOI10.1007/978-3-319-41114-9_12zbMath1476.68132OpenAlexW2492942125MaRDI QIDQ2829979

Juraj Šebej, Galina Jirásková, Alexander Szabari

Publication date: 9 November 2016

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01633946/file/416473_1_En_12_Chapter.pdf

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Concatenation of regular languages and descriptional 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
• Magic numbers in the state hierarchy of finite automata
• Reversal on Regular Languages and Descriptional Complexity
• Kleene Star on Unary Regular Languages
• THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES
• MAGIC NUMBERS AND TERNARY ALPHABET
• On the Square of Regular Languages
• Kleene Closure on Regular and Prefix-Free Languages
• On the State Complexity of Complements, Stars, and Reversals of Regular Languages
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• MAGIC NUMBERS FOR SYMMETRIC DIFFERENCE NFAS

This page was built for publication: The Complexity of Languages Resulting from the Concatenation Operation