Layered automata: A canonical model for automata over infinite words

arXiv (Cornell University)

Abstract

We introduce layered automata, a subclass of alternating parity automata that generalises deterministic automata. Assuming a consistency property, these automata are history deterministic and 0-1 probabilistic. We show that every omega-regular language is recognised by a unique minimal consistent layered automaton, and that this canonical form can be computed in polynomial time from every layered or deterministic automaton. We further establish that for layered automata both consistency checking and inclusion testing can be performed in polynomial time. Much like deterministic finite automata, minimal consistent layered automata admit a characterisation based on congruences.

Authors 3

1. Antonio Casares

   University of Kaiserslautern · Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau

   Affiliation as printed

   University Kaiserslautern -Landau , Germany

2. Christof Löding Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University , Germany

3. Igor Walukiewicz

   Centre National de la Recherche Scientifique · Université de Bordeaux

   Affiliation as printed

   CNRS , Bordeaux University , France