@inproceedings{FPS13,
keywords={perso},
  title     = {Emptiness Of Alternating Tree Automata Using Games With Imperfect Information},
  author    = {Nathanaël Fijalkow and
               Sophie Pinchinat and
               Olivier Serre},
year={2013},
booktitle = {Proceedings of the 33rd International Conference on Foundations of Software Technology and Theoretical
               Computer Science (FST&TCS 2013)},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  series    = {LIPIcs},
  volume    = {24},
  pages     = {299-311},
abstract = {We consider the emptiness problem for alternating tree automata, with two acceptance semantics: classical (all branches are accepted) and qualitative (almost all branches are accepted). For the classical semantics, the usual technique to tackle this problem relies on a Simulation Theorem which constructs an equivalent non-deterministic automaton from the original alternating one, and then checks emptiness by a reduction to a two-player perfect information game. However, for the qualitative semantics, no simulation of alternation by means of non-determinism is known. We give an alternative technique to decide the emptiness problem of alternating tree automata, that does not rely on a Simulation Theorem. Indeed, we directly reduce the emptiness problem to solving an imperfect information two-player parity game. Our new approach can successfully be applied to both semantics, and yields decidability results with optimal complexity; for the qualitative semantics, the key ingredient in the proof is a positionality result for stochastic games  played over infinite graphs.},
fulltexturl = {https://hal.inria.fr/hal-01260682},
}

{"_id":"y8NS26PseYi2jmcDb","bibbaseid":"fijalkow-pinchinat-serre-emptinessofalternatingtreeautomatausinggameswithimperfectinformation-2013","downloads":0,"creationDate":"2017-11-28T18:01:09.134Z","title":"Emptiness Of Alternating Tree Automata Using Games With Imperfect Information","author_short":["Fijalkow, N.","Pinchinat, S.","Serre, O."],"year":2013,"bibtype":"inproceedings","biburl":"https://www.irif.fr/~serre/bibtex/conferences.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","keywords":"perso","title":"Emptiness Of Alternating Tree Automata Using Games With Imperfect Information","author":[{"firstnames":["Nathanaël"],"propositions":[],"lastnames":["Fijalkow"],"suffixes":[]},{"firstnames":["Sophie"],"propositions":[],"lastnames":["Pinchinat"],"suffixes":[]},{"firstnames":["Olivier"],"propositions":[],"lastnames":["Serre"],"suffixes":[]}],"year":"2013","booktitle":"Proceedings of the 33rd International Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS 2013)","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","series":"LIPIcs","volume":"24","pages":"299-311","abstract":"We consider the emptiness problem for alternating tree automata, with two acceptance semantics: classical (all branches are accepted) and qualitative (almost all branches are accepted). For the classical semantics, the usual technique to tackle this problem relies on a Simulation Theorem which constructs an equivalent non-deterministic automaton from the original alternating one, and then checks emptiness by a reduction to a two-player perfect information game. However, for the qualitative semantics, no simulation of alternation by means of non-determinism is known. We give an alternative technique to decide the emptiness problem of alternating tree automata, that does not rely on a Simulation Theorem. Indeed, we directly reduce the emptiness problem to solving an imperfect information two-player parity game. Our new approach can successfully be applied to both semantics, and yields decidability results with optimal complexity; for the qualitative semantics, the key ingredient in the proof is a positionality result for stochastic games played over infinite graphs.","fulltexturl":"https://hal.inria.fr/hal-01260682","bibtex":"@inproceedings{FPS13,\nkeywords={perso},\n title = {Emptiness Of Alternating Tree Automata Using Games With Imperfect Information},\n author = {Nathanaël Fijalkow and\n Sophie Pinchinat and\n Olivier Serre},\nyear={2013},\nbooktitle = {Proceedings of the 33rd International Conference on Foundations of Software Technology and Theoretical\n Computer Science (FST&TCS 2013)},\n publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},\n series = {LIPIcs},\n volume = {24},\n pages = {299-311},\nabstract = {We consider the emptiness problem for alternating tree automata, with two acceptance semantics: classical (all branches are accepted) and qualitative (almost all branches are accepted). For the classical semantics, the usual technique to tackle this problem relies on a Simulation Theorem which constructs an equivalent non-deterministic automaton from the original alternating one, and then checks emptiness by a reduction to a two-player perfect information game. However, for the qualitative semantics, no simulation of alternation by means of non-determinism is known. We give an alternative technique to decide the emptiness problem of alternating tree automata, that does not rely on a Simulation Theorem. Indeed, we directly reduce the emptiness problem to solving an imperfect information two-player parity game. Our new approach can successfully be applied to both semantics, and yields decidability results with optimal complexity; for the qualitative semantics, the key ingredient in the proof is a positionality result for stochastic games played over infinite graphs.},\nfulltexturl = {https://hal.inria.fr/hal-01260682},\n}\n\n\n","author_short":["Fijalkow, N.","Pinchinat, S.","Serre, O."],"key":"FPS13","id":"FPS13","bibbaseid":"fijalkow-pinchinat-serre-emptinessofalternatingtreeautomatausinggameswithimperfectinformation-2013","role":"author","urls":{},"keyword":["perso"],"downloads":0},"search_terms":["emptiness","alternating","tree","automata","using","games","imperfect","information","fijalkow","pinchinat","serre"],"keywords":["perso"],"authorIDs":["5a1da46565b42fc01800000f"],"dataSources":["ymsPGsaH2xrv3xowd"]}