← All problems
Unverified

Is the Hierarchy of Valence Systems with Open Reachability Proper?

Starting from finite state automata, one can create a hierarchy of automata models by repeatedly applying one of the following constructions: Adding VASS counters (i.e. over N\mathbb{N}, without zero tests), and Building stacks containing the model. As a special case, we get, for example: FSA\mathsf{FSA} with N\mathbb{N}-counters =VASS= \mathsf{VASS} Stacks over FSA\mathsf{FSA} =PDA= \mathsf{PDA} PDA\mathsf{PDA} with N\mathbb{N}-counters =PVASS= \mathsf{PVASS} It would be interesting to know whether this hierarchy is proper, or if it collapses at some level. A first avenue of investigation might be to consider the hierarchy created by building stacks and adding Z\mathbb{Z}-counters.

Coming soon

Organizer

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