Publication Details

Summaries for Context-Free Games

HOLÍK Lukáš, MEYER Roland and MUSKALLA Sebastian. Summaries for Context-Free Games. In: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2016, pp. 41-57. ISBN 978-3-95977-027-9. Available from: http://drops.dagstuhl.de/opus/volltexte/2016/6876
Czech title
Souhrny pro bezkontextové gramatiky
Type
conference paper
Language
english
Authors
Holík Lukáš, Mgr., Ph.D. (DITS FIT BUT)
Meyer Roland (UNIKL)
Muskalla Sebastian (UNIKL)
URL
Keywords
summaries, context-free games, Kleene iteration, transition monoid, strategy synthesis
Abstract

We study two-player games played on the infinite graph of sentential forms induced by a context-free grammar (that comes with an ownership partitioning of the non-terminals). The winning condition is inclusion of the derived terminal word in the language of a finite automaton. Our contribution is a new algorithm to decide the winning player and to compute her strategy. It is based on a novel representation of all plays starting in a non-terminal. The representation uses the domain of Boolean formulas over the transition monoid of the target automaton. The elements of the monoid are essentially procedure summaries, and our approach can be seen as the first summary-based algorithm for the synthesis of recursive programs. We show that our algorithm has optimal (doubly exponential) time complexity, that it is compatible with recent antichain optimizations, and that it admits a lazy evaluation strategy. Our preliminary experiments indeed show encouraging results, indicating a speed up of three orders of magnitude over a competitor. 
Published
2016
Pages
41-57
Proceedings
36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Series
Leibniz International Proceedings in Informatics (LIPIcs)
Conference
36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Chennai Mathematical Institute, Chennai, India, CZ
ISBN
978-3-95977-027-9
Publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place
Dagstuhl, DE
DOI
BibTeX
@INPROCEEDINGS{FITPUB11338,
   author = "Luk\'{a}\v{s} Hol\'{i}k and Roland Meyer and Sebastian Muskalla",
   title = "Summaries for Context-Free Games",
   pages = "41--57",
   booktitle = "36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)",
   series = "Leibniz International Proceedings in Informatics (LIPIcs)",
   year = 2016,
   location = "Dagstuhl, DE",
   publisher = "Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik",
   ISBN = "978-3-95977-027-9",
   doi = "10.4230/LIPIcs.FSTTCS.2016.41",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11338"
}
Back to top