A1 Refereed original research article in a scientific journal

Decision Problems on Unary Probabilistic and Quantum Automata




AuthorsMika Hirvensalo, Abuzer Yakaryilmaz

PublisherUniversity of Latvia

Publication year2016

JournalBaltic Journal of Modern Computing

Journal acronymBJMC

Volume4

Issue4

First page 965

Last page976

Number of pages12

ISSN2255-8942

eISSN2255-8950

DOIhttps://doi.org/10.22364/bjmc.2016.4.4.22(external)


Abstract

It is well known that the emptiness problem for binary probabilistic automata and so
for quantum automata is undecidable. We present the current status of the emptiness problems
for unary probabilistic and quantum automata with connections with Skolem’s and positivity
problems. We also introduce the concept of linear recurrence automata in order to show the
connection naturally. Then, we also give possible generalizations of linear recurrence relations
and automata on vectors



Last updated on 2024-26-11 at 23:14