Deterministic asynchronous automata for infinite traces |
| |
Authors: | Volker Diekert Anca Muscholl |
| |
Affiliation: | (1) Institut für Informatik, Universität Stuttgart, Breitwiesenstrasse 20-22, D-70565 Stuttgart, Germany |
| |
Abstract: | This paper shows the equivalence between the family of recognizable languages over infinite traces and the family of languages which are recognized by deterministic asynchronous cellular Muller automata. We thus give a proper generalization of McNaughton's Theorem from infinite words to infinite traces. Thereby we solve one of the main open problems in this field. As a special case we obtain that every closed (w.r.t. the independence relation) word language is accepted by someI-diamond deterministic Muller automaton.This research has been supported by the ESPRIT Basic Research Action No. 6317 ASMICS 2. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |