Institute of

Theoretical Computer Science

Carl-Friedrich-Gauß-Fakultät

Technische Universität Braunschweig

FSTTCS 2016 - RIGG

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

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.

We compared three algorithms:
  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.
We tested several combinations x/y/z, where x specifies the number of states of the automaton, y is the number of terminal symbols and z is the number of non-terminals for each player. For each combination, we tried out 50 randomly generated instances. We measured the number of tries in which the algorithms could solve the instances within 10 seconds, and how much time was consumed for the instances that could be solved on average. The times are given in milliseconds.

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
5/ 5/10 5.4 4 7.4 0 701.7 0
5/10/ 5 13.9 0 0.3 0 375.7 0
5/ 5/15 6.0 0 1.1 0 1618.6 0
5/10/10 32.0 2 122.1 0 2214.4 0
5/15/ 5 44.5 0 0.2 0 620.7 0
5/ 5/20 3.4 0 1.4 0 3434.6 4
5/10/15 217.7 0 7.4 0 5263.0 16
10/ 5/ 5 8.8 2 0.6 0 2737.8 2
10/ 5/10 9.0 6 69.8 0 6484.9 66
15/ 5/ 5 30.7 0 0.2 0 5442.4 52
10/10/ 5 9.7 0 0.2 0 7702.1 92
10/15/15 252.3 0 1.9 0 n/a 100
10/15/20 12.9 0 1.8 0 n/a 100