Normal-closure-equivalence of RAAG- and counter-automata
A RAAG (right-angled Artin group) or graph group is defined by a finite undirected graph as follows: The resulting group has a generator for every vertex . Whenever two vertices are connected by an edge, then the respective generators are defined to commute. In other words, the group has the presentation By -VASS I mean a finite automaton with an additional "counter" with values in . On each transition the automaton can add a value to the counter, but the counter cannot be accessed; only when the automaton reaches an accepting state and the counter has value (trivial element of ), the input word is accepted. The normal closure of a language is its closure under concatenation and cyclic rotation. Two languages are nc-equivalent if they have the same normal closure. I know: If the graph of is not a transitive forest (equivalently: contains a cycle of length or a line of length at least as induced subgraph), then the class of -VASS languages is the class of recursive languages. Furthermore, for any -VASS there exists a -VASS for some such that and are nc-equivalent. Question: Does this extend to -VASS for being defined by a transitive forest, i.e. is every such -VASS language nc-equivalent to a -VASS language? A language is -context-free if it is the intersection of context-free languages. A language is poly-context-free if it is -context-free for some . Question: What is the relation between poly-context-free languages and -VASS or -VASS languages for RAAGs ? What is their nc-equivalence status?
