A simple undecidable problem: the inclusion problem for finite substitutions on \(ab^* c\)
From MaRDI portal
Publication:1887138
DOI10.1016/S0890-5401(03)00120-2zbMath1082.68054OpenAlexW2071584992MaRDI QIDQ1887138
L. P. Lisovik, Juhani Karhumäki
Publication date: 23 November 2004
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0890-5401(03)00120-2
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the equivalence of some transductions involving letter to letter morphisms on regular languages
- The undecidability of some equivalence problems concerning ngsm's and finite substitutions
- Equivalence problems for transducers with a bounded number of states
- The commutation of finite sets: A challenging problem
- The equivalence problem for finite substitutions in a regular language
- Conway's problem for three-word sets.
- On some transducer equivalence problems for families of languages
- On the equivalence problem for binary DOL systems
- An undecidable problem for countable markov chains
- Undecidability of the equivalence of finite substitutions on regular language
