← All problems
Unverified

Normal-closure-equivalence of RAAG- and counter-automata

A RAAG (right-angled Artin group) or graph group is defined by a finite undirected graph (V,E)(V,E) as follows: The resulting group has a generator xvx_v for every vertex v∈Vv \in V. Whenever two vertices are connected by an edge, then the respective generators are defined to commute. In other words, the group has the presentation ⟨xv∣xvxw=xwxv,(v,w)∈E⟩.\langle x_v \mid x_vx_w=x_wx_v, (v,w) \in E\rangle. By GG-VASS I mean a finite automaton with an additional "counter" with values in GG. 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 00 (trivial element of GG), the input word is accepted. The normal closure of a language LL 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 GG is not a transitive forest (equivalently: contains a cycle of length 44 or a line of length at least 44 as induced subgraph), then the class of GG-VASS languages is the class of recursive languages. Furthermore, for any F2×ZdF_2 \times \mathbb{Z}^d-VASS A\mathcal{A} there exists a Zn\mathbb{Z}^n-VASS A′\mathcal{A}' for some nn such that L(A)\mathcal{L}(\mathcal{A}) and L(A′)\mathcal{L}(\mathcal{A}') are nc-equivalent. Question: Does this extend to GG-VASS for GG being defined by a transitive forest, i.e. is every such GG-VASS language nc-equivalent to a Zn\mathbb{Z}^n-VASS language? A language is kk-context-free if it is the intersection of kk context-free languages. A language is poly-context-free if it is kk-context-free for some kk. Question: What is the relation between poly-context-free languages and Zn\mathbb{Z}^n-VASS or GG-VASS languages for RAAGs GG? What is their nc-equivalence status?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu