The Complexity of Languages Resulting from the Concatenation Operation
From MaRDI portal
Publication:2829979
DOI10.1007/978-3-319-41114-9_12zbMATH Open1476.68132OpenAlexW2492942125MaRDI QIDQ2829979FDOQ2829979
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
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
- Title not available (Why is that?)
- The state complexities of some basic operations on regular languages
- On the State Complexity of Complements, Stars, and Reversals of Regular Languages
- Title not available (Why is that?)
- Title not available (Why is that?)
- Magic numbers in the state hierarchy of finite automata
- STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
- Title not available (Why is that?)
- 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
- Reversal on regular languages and descriptional complexity
- The magic number problem for subregular language families
- Magic numbers and ternary alphabet
- MAGIC NUMBERS FOR SYMMETRIC DIFFERENCE NFAS
- Concatenation of regular languages and descriptional complexity
- Kleene star on unary regular languages
- On the square of regular languages
- Kleene Closure on Regular and Prefix-Free Languages
Cited In (6)
- Orthogonal concatenation: language equations and state complexity
- On interpretability in the theory of concatenation
- The complexity of concatenation on deterministic and alternating finite automata
- Concatenation of Regular Languages and Descriptional Complexity
- State complexity of multiple catenations
- The complexity of languages resulting from the concatenation operation
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)
