Theoretical Computer Science

FSTTCS 2016 - RIGG

This web page accompanies our FSTTCS 2016 submissions Summaries for Context-Free Games. Here you can

• find information about our tool RIGG, and
• inspect the experiments conducted for the above submission.

RIGG

The tool is written in C++-project, developed for MinGW64, GCC 4.8.3. A CMake project file (e.g. for usage with CLion) is contained.

Note that the classes used for benchmarking use Windows system functions and may not work under Linux / MacOS.

The source code is available on GitHUB.

Experimental Results

The results are listed in the table below. For experiments we used an Intel i7-6700K running at 4 GHz and tested our tool on randomly generated automata and grammars.

• The automata were generated according to the Tabakov-Vardi-model.
• The linear context-free grammars grammars were generated according to an analogue of the Tabakov-Vardi-model for context-free Grammars with rules of the shape X → aYb
• Since sparse automata and grammars are likely to yield simpler instances, we focus on dense examples.

1. Our algorithm with a naive Kleene iteration, i.e. all components of the current solution are updated in each step.
2. Our algorithm with chaotic iteration implemented using a worklist, i.e. only components whose dependencies have been updated are modified. This is the common way of implementing a Kleene iteration.
3. Cachat's algorithm applied to an encoding of our problem as pushdown system. Note that the encoding causes an exponential blowup, which is to be expected since the problem is 2EXPTIME-complete, and Cachat's algorithm is exponential. To improve the runtime, the target automaton has been minimized before creating the pushdown system.