On the complexity of decidable cases of the commutation problem of languages
From MaRDI portal
Publication:557812
DOI10.1016/j.tcs.2004.03.073zbMath1077.68045OpenAlexW2015733266MaRDI QIDQ557812
Wojciech Plandowski, Wojciech Rytter, Juhani Karhumäki
Publication date: 30 June 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.03.073
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Complexity measures for regular expressions
- The commutation of finite sets: A challenging problem
- Conway's problem for three-word sets.
- Some decision problems concerning semilinearity and commutation.
- Codes et motifs
- Satisfiability of word equations with constants is in PSPACE
- `` Strong NP-Completeness Results
- Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the complexity of decidable cases of the commutation problem of languages
