Where academic tradition
meets the exciting future

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