On the Regular Emptiness Problem of Subzero Automata

ENS-Lyon; France); Henryk Michalewski (University of Warsaw; Matteo Mio (CNRS; Miko{\l}aj Boja\'nczyk (University of Warsaw; Poland)

arxiv: 1608.03319 · v1 · pith:OTCMFULKnew · submitted 2016-08-11 · 💻 cs.FL · cs.LO

On the Regular Emptiness Problem of Subzero Automata

Henryk Michalewski (University of Warsaw , Poland) , Matteo Mio (CNRS , ENS-Lyon , France) , Miko{\l}aj Boja\'nczyk (University of Warsaw This is my paper

classification 💻 cs.FL cs.LO

keywords automatasubzeroproblemregulartreeacceptanceacceptsautomaton

0 comments

read the original abstract

Subzero automata is a class of tree automata whose acceptance condition can express probabilistic constraints. Our main result is that the problem of determining if a subzero automaton accepts some regular tree is decidable.

This paper has not been read by Pith yet.

On the Regular Emptiness Problem of Subzero Automata

discussion (0)