8 papers
The boundedness and zero isolation problems for weighted automata over nonnegative rationals
Wojciech Czerwiński, Engel Lefaucheux, Filip Mazowiecki +2
We consider linear cost-register automata (equivalent to weighted automata) over the semiring of nonnegative rationals, which generalise probabilistic automata. The two problems of…
Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes
Wojciech Czerwiński, Łukasz Orlikowski
We study the complexity of the reachability problem for Vector Addition Systems with States (VASSes) in fixed dimensions. We provide four lower bounds improving the currently known…
Language Inclusion for Boundedly-Ambiguous Vector Addition Systems is Decidable
Wojciech Czerwiński, Piotr Hofman
We consider the problems of language inclusion and language equivalence for Vector Addition Systems with States (VASS) with the acceptance condition defined by the set of accepting…
Reachability in Vector Addition Systems is Ackermann-complete
Wojciech Czerwiński, Łukasz Orlikowski
Vector Addition Systems and equivalent Petri nets are a well established models of concurrency. The central algorithmic problem for Vector Addition Systems with a long research his…
New Techniques for Universality in Unambiguous Register Automata
Wojciech Czerwiński, Antoine Mottet, Karin Quaas
Register automata are finite automata equipped with a finite set of registers ranging over the domain of some relational structure like or . Register…
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
Jiehua Chen, Wojciech Czerwiński, Yann Disser +8
We present a data structure that in a dynamic graph of treedepth at most , which is modified over time by edge insertions and deletions, maintains an optimum-height elimination…
Reachability in fixed dimension vector addition systems with states
Wojciech Czerwiński, Sławomir Lasota, Ranko Lazić +2
The reachability problem is a central decision problem for formal verification based on vector addition systems with states (VASS), which are equivalent to Petri nets and form one…
Regular Separability of Well Structured Transition Systems
Wojciech Czerwiński, Sławomir Lasota, Roland Meyer +3
We investigate the languages recognized by well-structured transition systems (WSTS) with upward and downward compatibility. Our first result shows that, under very mild assumption…