Finite Substitutions and Integer Weighted Finite Automata
Vesa Halava · 1998
In this work we present a new chain of undecidability reductions, which begins from the classical halting problem of Turing machines and ends to the undecidability proof of the equivalence problem for finite substitutions on regular languages in Chapter 4. This undecidability result was originally proved by L. Lisovik in 1997. We present a new proof, which is shorter and more elementary than the original one. Our proof uses the undecidability of the universe problem for the integer weighted finite automata. An integer weighted nite automaton is a finite automaton, which has integer weights on its edges. This automaton accepts an input word, if there exists a path reading the word such that the sum of the weights of the used edges is zero. In the universe problem we ask whether a given integer weighted finite automaton accepts all its input words. This problem is proved undecidable in Chapter 3. The proof uses the undecidability of a certain modication of the Post Correspondence Problem, proved...