## Undecidability of the Universality Problem for 3-State Integer Weighted Büchi Automata

Vesa Halava, Tero Harju, Reino Niskanen, Igor Potapov, Undecidability of the Universality Problem for 3-State Integer Weighted Büchi Automata. TUCS Technical Reports 1105, TUCS, 2014.

### Abstract:

We show that the universe problem L(A)=B^\omega is undecidable for 3-state
finite automata A with an integer weight function g on its transitions.
The language L(A) is the set of all infinite words w in B^\omega for which
there exists a path (i.e., a computation) in A that visits the accepting state infinitely
often with weight zero. The model A can be consider as a generalization of
the Büchi automaton with weights from the additive group of integers.

### Files:

Full publication in PDF-format

### BibTeX entry:

@TECHREPORT{tHaHaNiPo14a,  title = {Undecidability of the Universality Problem for 3-State Integer Weighted Büchi Automata},  author = {Halava, Vesa and Harju, Tero and Niskanen, Reino and Potapov, Igor},  number = {1105},  series = {TUCS Technical Reports},  publisher = {TUCS},  year = {2014},  keywords = {weighted Büchi automaton, universe problem, undecidability, infinite PCP},  ISBN = {978-952-12-3029-5},}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication