• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages

Mika Hirvensalo, Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages. TUCS Technical Reports 769, Turku Centre for Computer Science, 2006.

Abstract:

We give constructions of probabilistic and MO-type quantum automata
that have undecidable emptiness problem for the cut-point languages. The
sizes of the automata over a binary alphabet are 25 and 21, rather than
47 and 43 given in [1] and [2], respectively.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tHirvensalo06a,
  title = {Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages},
  author = {Hirvensalo, Mika},
  number = {769},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2006},
  keywords = {Undecidability, Stochastic Automata, Probabilistic Automata, Quantum Automata, Post Correspondence Problem, Cut-Point Languages},
  ISBN = {952-12-1726-X},
}

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

Edit publication