Scaffolding Automata
Such an automaton is a computing machine which constructs a labelled, directed, acyclic graph of bounded degree, which we call a scaffold. At the start of the computation, the graph is a single node with a special end-marker label; this is the base of the scaffold. Then as the computation proceeds new input symbols are read and new nodes are added; the node which was last added is called the top of the scaffold. At each step of computation, the scaffolding automaton sees a new input symbol, and is allowed to look at a finite-distance neighbourhood of the top; based on the edges which are present, on the labels it sees, on the input symbol it just read, and on the current state of its finite control, the automaton adds a new node to the scaffold (the new top), and chooses the edges of this new node to point to some nodes in the finite-distance neighbourhood it has just observed. This is repeated until all input symbols are read.
Can recognize PEG languages.
Open questions
- Is it subclass of NSA?