On the Regular Emptiness Problem of Subzero Automata

Henryk Michalewski
(University of Warsaw, Poland)
Matteo Mio
(CNRS and ENS-Lyon, France)
Mikołaj Bojańczyk
(University of Warsaw, Poland)

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.

In Massimo Bartoletti, Ludovic Henrio, Sophia Knight and Hugo Torres Vieira: Proceedings 9th Interaction and Concurrency Experience (ICE 2016), Heraklion, Greece, 8-9 June 2016, Electronic Proceedings in Theoretical Computer Science 223, pp. 1–23.
Published: 10th August 2016.

ArXived at: https://dx.doi.org/10.4204/EPTCS.223.1 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org