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.
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.
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.
- Our algorithm with a naive Kleene iteration, i.e. all components of the current solution are updated in each step.
- 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.
- 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.
|Naive Kleene||Worklist Kleene||Cachat|
|avg. time||% timeout||avg. time||% timeout||avg. time||% timeout|
|5/ 5/ 5||65.2||2||0.8||0||94.7||0|
|10/ 5/ 5||8.8||2||0.6||0||2737.8||2|
|15/ 5/ 5||30.7||0||0.2||0||5442.4||52|