Undecidability in Finite Transducers, Defense Systems and Finite Substitutions

2021/11/30 by Vesa Halava, Halava, Vesa
Computer Science · #03D35 #68Q45 #Computability, Logic, AI Algorithms #Computation and Language (cs.CL) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic, programming, and type systems #Natural Language Processing Techniques #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2111.15420

openalex publication_date 2021/11/30 · openalex created_date 2022/11/08 · openalex updated_date 2026/07/28

Abstract

<p> In this manuscript we present a detailed proof for undecidability of the equivalence of finite substitutions on regular language <span><em>b</em><span></span><span>0</span><span>,</span><span>1</span><span>*</span><span></span><em>c</em></span>. The proof is based on the works of Leonid P. Lisovik. <br></p>

Related

• On Equivalence and Uniformisation Problems for Finite Transducers
• Regular languages defined by first-order formulas without quantifier alternation
• Undecidability in First-Order Theories of Term Algebras Extended with a\n Substitution Operator
• Complete Compositional Syntax for Finite Transducers on Finite and Bi-Infinite Words
• Characterization and Decidability of FC-Definable Regular Languages