7 citations · 21 across the 10 of their papers we have counts for
Showing 2023Show all
2 papers · 1 filter
cs.FL2023
History-deterministic Vector Addition Systems
Sougata Bose, David Purser, Patrick Totzke
We consider history-determinism, a restricted form of non-determinism, for Vector Addition Systems with States (VASS) when used as acceptors to recognise languages of finite words.…
cs.FL2023
The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)
Laure Daviaud, David Purser, Marie Tcheng
We show that the big-O problem for max-plus automata is decidable and PSPACE-complete. The big-O (or affine domination) problem asks whether, given two max-plus automata computing…