HOLÍK Lukáš, MEYER Roland and MUSKALLA Sebastian. Summaries for ContextFree Games. In: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Dagstuhl: Schloss DagstuhlLeibnizZentrum fuer Informatik, 2016, pp. 4157. ISBN 9783959770279. Available from: http://drops.dagstuhl.de/opus/volltexte/2016/6876 
Publication language:  english 

Original title:  Summaries for ContextFree Games 

Title (cs):  Souhrny pro bezkontextové gramatiky 

Pages:  4157 

Proceedings:  36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) 

Conference:  36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) 

Series:  Leibniz International Proceedings in Informatics (LIPIcs) 

Place:  Dagstuhl, DE 

Year:  2016 

URL:  http://drops.dagstuhl.de/opus/volltexte/2016/6876 

ISBN:  9783959770279 

Publisher:  Schloss DagstuhlLeibnizZentrum fuer Informatik 

Files:  


Keywords 

summaries, contextfree games, Kleene iteration, transition monoid, strategy synthesis 
Annotation 

We study twoplayer games played on the infinite graph of sentential forms induced by a contextfree grammar (that comes with an ownership partitioning of the nonterminals). 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 nonterminal. 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 summarybased 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. 
BibTeX: 

@INPROCEEDINGS{
author = {Luk{\'{a}}{\v{s}} Hol{\'{i}}k and Roland Meyer and Sebastian
Muskalla},
title = {Summaries for ContextFree Games},
pages = {4157},
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 DagstuhlLeibnizZentrum fuer Informatik},
ISBN = {9783959770279},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php.en.iso88592?id=11338}
} 