5 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…
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…