On the Regular Emptiness Problem of Subzero Automata

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.

Saved in:
Bibliographic Details
Published in:Electronic proceedings in theoretical computer science 2016-08, Vol.223 (Proc. ICE 2016), p.1-23
Main Authors: Michalewski, Henryk, Mio, Matteo, Bojańczyk, Mikołaj
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2075-2180
2075-2180
DOI:10.4204/EPTCS.223.1