DETERMINISTIC ASYNCHRONOUS AUTOMATA FOR INFINITE TRACES

Authors
DIEKERT V MUSCHOLL A
Citation
V. Diekert et A. Muscholl, DETERMINISTIC ASYNCHRONOUS AUTOMATA FOR INFINITE TRACES, Acta informatica, 31(4), 1994, pp. 379-397
Citations number
21
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Acta informatica → ACNP
ISSN journal
00015903
Volume
31
Issue
4
Year of publication
1994
Pages
379 - 397
Database
ISI
SICI code
0001-5903(1994)31:4<379:DAAFIT>2.0.ZU;2-W
Abstract
This paper shows the equivalence between the family of recognizable la nguages over infinite traces and the family of languages which are rec ognized by deterministic asynchronous cellular Muller automata. We thu s give a proper generalization of McNaughton's Theorem from infinite w ords to infinite traces. Thereby we solve one of the main open problem s in this field. As a special case we obtain that every closed (w.r.t. the independence relation) word language is accepted by some I-diamon d deterministic Muller automaton.