Moore Machines from the papers by Rivest and Schapire

Related publications: [RS93] [RS94]

Description

This benchmark contains Moore machines from the papers by Rivest and Schapire, rendered in dot format. Below are descriptions from the papers. The first is from [RS93]. The other two are from [RS94]. The latter are smaller if you consider the "inverse deterministic" Moore machines. These are called "diversity-based." The descriptions from the papers are ambiguous. For example, I had to choose the initial state myself.

1. In the "Crossword Puzzle" environment, the robot is on a crossword puzzle grid. The robot has three actions available to it: it can step ahead one square, or it can turn left or right by 90 degrees. The robot can only occupy the white squares of the crossword puzzle; an attempt to move onto a black square is a "no-op." Attempting to step beyond the boundaries of the puzzle is also a no-op. Each of the four "walls" of the puzzle has been painted a different color. The robot looks as far ahead as possible in the direction it faces: if its view is obstructed by a black square, then it sees "black;" otherwise, it sees the color of the wall it is facing. Thus, the robot has five possible sensations. Since this environment is essentially a maze, it may contain regions which are difficult to reach or difficult to get out of.
2. The n*n grid World. Consider a robot on an n X n square grid (with “wraparound,” so that is is topologically a torus). The robot is on one of the squares and is facing in one of the four possible directions. Each square (except the one it currently occupies) is either red, green, or blue. The robot can sense the color of the square it is facing. The following actions are available to the robot: It can paint the square it faces red, geen, or blue. The robot can turn left or right by 90 degrees, or step forward one square in the direction it is facing. Stepping ahead has the curious side effect of causeing the square it previously occupied to be painted the color of the square it has just moved to, so moving around causes the coloring to get scrabled up.
3. In this environment, the robot is able to read the leftmost bit of an n-bit register, such as the 10-bit register depicted in Figure 1. Its actions allow it to rotate the register left or right (with wraparound) or to flip the bit it sees. Clearly, this automaton consists of 2^n global states, but its diversity is only 2n since there is one test for each bit, and one for the complement note that the register world is a permutation automaton.