Summaries for Context-Free Games
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
16
Series
36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016), pp. 1-16, Leibniz International Proceedings in Informatics ; Volume 65
Abstract
We study two-player games played on the infinite graph of sentential forms induced by a contextfree 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.Description
Keywords
Other note
Citation
Holik, L, Meyer, R & Muskalla, S 2016, Summaries for Context-Free Games. in A Lal, S Akshay, S Saurabh & S Sen (eds), 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)., 41, Leibniz International Proceedings in Informatics, vol. 65, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-16, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Chennai, India, 13/12/2016. https://doi.org/10.4230/LIPIcs.FSTTCS.2016.41