ω-rational Languages: High Complexity Classes vs. Borel Hierarchy

Description

The paper investigates classes of languages of innite words with respect to the acceptance conditions of the nite automata recognizing them. Some new natural classes are compared with the Borel hierachy. In particular, it is proved that (fin, =) is as high as F R σ and G R δ. As a side eect, it is also proved that in this last case, considering or not considering the initial state of the FA makes a substantial dierence. Languages over innite words have been used since the very introduction of symbolic dynamics. Afterwards, they have spread in a multitude of scientic elds. Computer science is more directly concerned for example by their application in formal specication and verication, game theory, logics, etc.. ω-rational languages have been introduced as a natural extension of languages of nite words recognized by nite automata. Indeed, a nite automaton accepts some input u if at the end of the reading of u, the automaton reaches a nal state. Clearly, when generalizing to innite words, this accepting condition has to be changed. For this reason, new accepting conditions have been introduced in literature. For example, an innite word w is accepted by a nite automaton A under the Büchi acceptance condition if and only if there exists a run of A which passes innitely often through a set of accepting states while reading w. Indeed, this was introduced by Richard Büchi in the seminal work [1] in 1960. Later on, David Muller characterized runs that pass through all elements of a given set of accepting states and visit them innitely often [8]. Afterwards, more acceptance conditions appeared in a series of papers [4,5,11,7,6]. Each of these

Abstract

International audience

Additional details