AAAI Publications, Thirteenth Artificial Intelligence and Interactive Digital Entertainment Conference

Font Size: 
Analyzing Expressionist Grammars by Reduction to Symbolic Visibly Pushdown Automata
Joseph C. Osborn, James Ryan, Michael Mateas

Last modified: 2017-09-19


We extend the Expressionist project, and thereby the re-emerging area of grammar-based text generation, by applying a technique from software verification to a critical search problem related to content generation from grammars. In Expressionist, authors attach tags (corresponding to pertinent meanings) to nonterminal symbols in a context-free grammar, which enables the targeted generation of content that expresses requested meanings (i.e., has the requested tags). While previous work has demonstrated methods for requesting content with a single required tag, requests for multiple tags yields a search task over domains that may realistically span quintillions or more elements. In this paper, we reduce Expressionist grammars to symbolic visibly pushdown automata, which allows us to locate in massive search spaces generable outputs that satisfy moderately complex criteria related to tags. While the satisficing of more complex tag criteria is still not feasible using this technique, we forecast a number of opportunities for future directions.


symbolic visibly pushdown automata; grammars; formal methods; natural language generation

Full Text: PDF