Skip to Main content Skip to Navigation
Reports

Emptiness Of Alternating Parity Tree Automata Using Games With Imperfect Information

Sophie Pinchinat 1 Olivier Serre 2 
1 S4 - System synthesis and supervision, scenarios
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : We focus on the emptiness problem for alternating parity tree automata. The usual technique to tackle this problem first removes alternation, going to non-determinism, and then checks emptiness by reduction to a two-player perfect-information parity game. In this note, we give an alternative roadmap to this problem by providing a direct reduction to the emptiness problem to solving an imperfect-information two-player parity game.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-00700334
Contributor : Sophie Pinchinat Connect in order to contact the contributor
Submitted on : Tuesday, May 22, 2012 - 4:41:53 PM
Last modification on : Friday, February 4, 2022 - 3:12:03 AM
Long-term archiving on: : Thursday, December 15, 2016 - 8:08:27 AM

File

RR-1992.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00700334, version 1

Citation

Sophie Pinchinat, Olivier Serre. Emptiness Of Alternating Parity Tree Automata Using Games With Imperfect Information. [Research Report] PI-1992, 2012, pp.6. ⟨hal-00700334⟩

Share

Metrics

Record views

248

Files downloads

396