A Playful Glance at Hierarchical Questions for Two-Way Alternating Automata

Fiche du document

Auteurs
Date

2009

Type de document
Périmètre
Langue
Identifiant
Source

Serveur académique Lausannois

Relations

Ce document est lié à :
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-03092-5_5

Ce document est lié à :
info:eu-repo/semantics/altIdentifier/isbn/978-3-642-03091-8

Ce document est lié à :
info:eu-repo/semantics/altIdentifier/urn/urn:nbn:ch:serval-BIB_EEF86EFB69D97

Collection

Serveur Académique Lausannois

Organisation

Université de Lausanne et CHUV

Licences

info:eu-repo/semantics/openAccess , Copying allowed only for non-profit organizations , https://serval.unil.ch/disclaimer

Mots-clés 0

µ-calculus; Backward modalities; Wadge games; Topological complexity; Parity games; Two-way alternating tree automata; Descriptive set theory

Sujets proches En

Automata Automatons Automata Abstract automata Abstract machines Mathematical machine theory

Citer ce document

J. Duparc et al., « A Playful Glance at Hierarchical Questions for Two-Way Alternating Automata », Serveur académique Lausannois, ID : 10.1007/978-3-642-03092-5_5

Métriques

Partage / Export

Résumé 0

Two-way alternating automata were introduced by Vardi in order to study the satisfiability problem for the modal μ-calculus extended with backwards modalities. In this paper, we present a very simple proof by way of Wadge games of the strictness of the hierarchy of Motowski indices of two-way alternating automata over trees.

document thumbnail

Par les mêmes auteurs

Sur les mêmes sujets

Exporter en