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 <>
Submitted on : Tuesday, May 22, 2012 - 4:41:53 PM
Last modification on : Tuesday, June 15, 2021 - 4:13:52 PM
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

571

Files downloads

547