The Complexity of Languages Resulting from the Concatenation Operation

DOI10.1007/978-3-319-41114-9_12MaRDI QIDQ2829979zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• The complexity of languages resulting from the concatenation operation
• Concatenation of regular languages and descriptional complexity
• Concatenation of Regular Languages and Descriptional Complexity
• scientific article; zbMATH DE number 1773089
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Orthogonal concatenation: language equations and state complexity
• The complexity of concatenation on deterministic and alternating finite automata
• Transition complexity of language operations
• Implementation and Application of Automata
• The range of state complexities of languages resulting from the cut operation

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (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?)
• A family of NFAs which need 2\(^{n}-\alpha\) deterministic states
• Concatenation of regular languages and descriptional complexity
• Kleene Closure on Regular and Prefix-Free Languages
• Kleene star on unary regular languages
• MAGIC NUMBERS FOR SYMMETRIC DIFFERENCE NFAS
• Magic numbers and ternary alphabet
• Magic numbers in the state hierarchy of finite automata
• On the State Complexity of Complements, Stars, and Reversals of Regular Languages
• On the square of regular languages
• Reversal on regular languages and descriptional complexity
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• The magic number problem for subregular language families
• The state complexities of some basic operations on regular languages
• Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs

Cited in

(6)

• State complexity of multiple catenations
• Concatenation of Regular Languages and Descriptional Complexity
• On interpretability in the theory of concatenation
• The complexity of concatenation on deterministic and alternating finite automata
• The complexity of languages resulting from the concatenation operation
• Orthogonal concatenation: language equations and state complexity

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

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