Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950573 | Information and Computation | 2017 | 12 Pages |
Abstract
We address the problem of providing a Borel-like classification of languages of infinite Mazurkiewicz traces, and provide a solution in the framework of Ï-automata over infinite words - which is invoked via the sets of linearizations of infinitary trace languages. We identify trace languages whose linearizations are recognized by deterministic weak or deterministic Büchi (word) automata. We present a characterization of the class of linearizations of all recognizable Ï-trace languages in terms of Muller (word) automata. Finally, we show that the linearization of any recognizable Ï-trace language can be expressed as a Boolean combination of languages recognized by our class of deterministic Büchi automata.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Namit Chaturvedi, Marcus Gelderie,