Abstract
In this manuscript we present a detailed proof for undecidability of the equivalence of finite substitutions on regular language b{0,1}^*c. The proof is based on the works of Leonid P. Lisovik.
Undecidability in Finite Transducers, Defense Systems and Finite Substitutions
Related papers
Ranked by semantic similarity — how closely each paper's abstract matches this one (100% = near-identical topic).
- Undecidability of the Lambek calculus with a relevant modality (2016)51% match
- Three Dogmas, a Puzzle and its Solution (2023)49% match
- Dung's semantics satisfy attack removal monotonicity (2020)49% match
- Kleene algebra with commutativity conditions is undecidable (2024)49% match
- Complexity and Avoidance (2022)49% match
- Optimal Unambiguous DNFs and Alon-Saks-Seymour (2026)49% match
- Positive-Data Learning of Fixed-Observation Linear MCFGs from Working Binary Presentations (2026)49% match
- A Quantitative Confirmation of the Currier Language Distinction (2026)48% match