Facchini, Alessandro and Murlak, Filip and Skrzypczak, Michal (2015) On the Weak Index Problem for Game Automata. In: Logic, Language, Information, and Computation WOLLIC 2015, Bloomington, Indiana.
Full text not available from this repository.Abstract
Game automata are known to recognise languages arbitrarily high in both the non-deterministic and alternating Rabin–Mostowski index hierarchies. Recently it was shown that for this class both hierarchies are decidable. Here we complete the picture by showing that the weak index hierarchy is decidable as well. We also provide a procedure computing for a game automaton an equivalent weak alternating automaton with the minimal index and a quadratic number of states. As a by-product we obtain that, as for deterministic automata, the weak index and the Borel rank coincide.
Item Type: | Article in conference proceedings or Presentation at a conference (Paper) |
---|---|
Additional Information: | DOI: 10.1007/978-3-662-47709-0 8 |
Subjects: | Computer sciences > Computer science |
Department/unit: | Dipartimento tecnologie innovative > Istituto Dalle Molle di studi sull’intelligenza artificiale USI-SUPSI |
Depositing User: | Alessandro Facchini |
Date Deposited: | 02 Jun 2015 06:59 |
Last Modified: | 02 Jun 2015 06:59 |
URI: | http://repository.supsi.ch/id/eprint/6520 |
Actions (login required)
View Item |