Sławomir Lasota
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Sławomir Lasota has a total of 76 co-authors. Here are the top co-authors by number of shared publications:
- Anna Gambin
Institute of Informatics, University of Warsaw, Stefana Banacha 2, Warsaw 02-097, Poland
9 shared publications - Bartek Klin
University of Warsaw
8 shared publications - Piotr Hofman
University of Warsaw
7 shared publications Wojciech Czerwiński
7 shared publicationsSibylle Fröschle
6 shared publications- Gregory Kucherov
LIGM CNRS Université Gustave Eiffel Marne-la-Vallée France
5 shared publications
Latest Publications
- 11 October 2026
- Published by Springer Nature
- p. 114-123
Reachability in 3-VAS
- 1 June 2026
- Published by Springer Nature
- p. 123-149
The Reachability Problem in Petri Nets: Decidability and Hardness
- 1 June 2026
- Published by Springer Nature
- p. 123-149
The Reachability Problem in Petri Nets: Decidability and Hardness
- Open Access
- 24 January 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (1) , 1-39
Orbit-finite Linear Programming
An infinite set is orbit-finite if, up to permutations of atoms, it has only finitely many elements. We study a generalisation of linear programming where constraints are expressed by an orbit-finite system of linear inequalities. As our principal contribution we provide a decision procedure for checking if such a system has a real solution, and for computing the minimal/maximal value of a linear objective function over the solution set. We also show undecidability of these problems in case when only integer solutions are considered. Therefore orbit-finite linear programming is decidable, while orbit-finite integer linear programming is not.
- 24 January 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (1) , 1-39
Open AccessOrbit-finite Linear Programming
An infinite set is orbit-finite if, up to permutations of atoms, it has only finitely many elements. We study a generalisation of linear programming where constraints are expressed by an orbit-finite system of linear inequalities. As our principal contribution we provide a decision procedure for checking if such a system has a real solution, and for computing the minimal/maximal value of a linear objective function over the solution set. We also show undecidability of these problems in case when only integer solutions are considered. Therefore orbit-finite linear programming is decidable, while orbit-finite integer linear programming is not.
- Open Access
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 1-14
Equivariant ideals of polynomials
We study existence and computability of finite bases for ideals of polynomials over infinitely many variables. In our setting, variables come from a countable logical structure A, and embeddings from A to A act on polynomials by renaming variables. First, we give a sufficient and necessary condition for A to guarantee the following generalisation of Hilbert's Basis Theorem: every polynomial ideal which is equivariant, i.e. invariant under renaming of variables, is finitely generated. Second, we develop an extension of classical Buchberger's algorithm to compute a Gröbner basis of a given equivariant ideal. This implies decidability of the membership problem for equivariant ideals. Finally, we sketch upon various applications of these results to register automata, Petri nets with data, orbitfinitely generated vector spaces, and orbit-finite systems of linear equations.
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 1-14
Open AccessEquivariant ideals of polynomials
We study existence and computability of finite bases for ideals of polynomials over infinitely many variables. In our setting, variables come from a countable logical structure A, and embeddings from A to A act on polynomials by renaming variables. First, we give a sufficient and necessary condition for A to guarantee the following generalisation of Hilbert's Basis Theorem: every polynomial ideal which is equivariant, i.e. invariant under renaming of variables, is finitely generated. Second, we develop an extension of classical Buchberger's algorithm to compute a Gröbner basis of a given equivariant ideal. This implies decidability of the membership problem for equivariant ideals. Finally, we sketch upon various applications of these results to register automata, Petri nets with data, orbitfinitely generated vector spaces, and orbit-finite systems of linear equations.
- Open Access
New Lower Bounds for Reachability in Vector Addition Systems
We investigate the dimension-parametric complexity of the reachability problem in vector addition systems with states (VASS) and its extension with pushdown stack (pushdown VASS). Up to now, the problem is known to be $\mathcal{F}_k$-hard for VASS of dimension $3k+2$ (the complexity class $\mathcal{F}_k$ corresponds to the $k$th level of the fast-growing hierarchy), and no essentially better bound is known for pushdown VASS. We provide a new construction that improves the lower bound for VASS: $\mathcal{F}_k$-hardness in dimension $2k+3$. Furthermore, building on our new insights we show a new lower bound for pushdown VASS: $\mathcal{F}_k$-hardness in dimension $\frac k 2 + 4$. This dimension-parametric lower bound is strictly stronger than the upper bound for VASS, which suggests that the (still unknown) complexity of the reachability problem in pushdown VASS is higher than in plain VASS (where it is Ackermann-complete).Open AccessNew Lower Bounds for Reachability in Vector Addition Systems
We investigate the dimension-parametric complexity of the reachability problem in vector addition systems with states (VASS) and its extension with pushdown stack (pushdown VASS). Up to now, the problem is known to be $\mathcal{F}_k$-hard for VASS of dimension $3k+2$ (the complexity class $\mathcal{F}_k$ corresponds to the $k$th level of the fast-growing hierarchy), and no essentially better bound is known for pushdown VASS. We provide a new construction that improves the lower bound for VASS: $\mathcal{F}_k$-hardness in dimension $2k+3$. Furthermore, building on our new insights we show a new lower bound for pushdown VASS: $\mathcal{F}_k$-hardness in dimension $\frac k 2 + 4$. This dimension-parametric lower bound is strictly stronger than the upper bound for VASS, which suggests that the (still unknown) complexity of the reachability problem in pushdown VASS is higher than in plain VASS (where it is Ackermann-complete). - Open Access
- 23 March 2021
- Published by Springer Nature
- Vol. 12650, 365-384
Nondeterministic and co-Nondeterministic Implies Deterministic, for Data Languages
We prove that if a data language and its complement are both recognized by nondeterministic register automata (without guessing), then they are also recognized by deterministic ones.
- 23 March 2021
- Published by Springer Nature
- Vol. 12650, 365-384
Open AccessNondeterministic and co-Nondeterministic Implies Deterministic, for Data Languages
We prove that if a data language and its complement are both recognized by nondeterministic register automata (without guessing), then they are also recognized by deterministic ones.
- 3 December 2020
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 117, 202-241
Reachability relations of timed pushdown automata
- 3 December 2020
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 117, 202-241
Reachability relations of timed pushdown automata
- 1 December 2020
- Published by Elsevier in Information and Computation
- Vol. 275
WQO dichotomy for 3-graphs
- 1 December 2020
- Published by Elsevier in Information and Computation
- Vol. 275
WQO dichotomy for 3-graphs
- Open Access
Reachability in fixed dimension vector addition systems with states
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 of the most studied and applied models of concurrency. Reachability for VASS is also inter-reducible with a plethora of problems from a number of areas of computer science. In spite of recent progress, the complexity of the reachability problem remains unsettled, and it is closely related to the lengths of shortest VASS runs that witness reachability. We consider VASS of fixed dimension, and obtain three main results. For the first two, we assume that the integers in the input are given in unary, and that the control graph of the given VASS is flat (i.e., without nested cycles). We obtain a family of VASS in dimension 3 whose shortest reachability witnessing runs are exponential, and we show that the reachability problem is NP-hard in dimension 7. These results resolve negatively questions that had been posed by the works of Blondin et al. in LICS 2015 and Englert et al. in LICS 2016, and contribute a first construction that distinguishes 3-dimensional flat VASS from 2-dimensional VASS. Our third result, by means of a novel family of products of integer fractions, shows that 4-dimensional VASS can have doubly exponentially long shortest reachability witnessing runs. The smallest dimension for which this was previously known is 14.
Open AccessReachability in fixed dimension vector addition systems with states
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 of the most studied and applied models of concurrency. Reachability for VASS is also inter-reducible with a plethora of problems from a number of areas of computer science. In spite of recent progress, the complexity of the reachability problem remains unsettled, and it is closely related to the lengths of shortest VASS runs that witness reachability. We consider VASS of fixed dimension, and obtain three main results. For the first two, we assume that the integers in the input are given in unary, and that the control graph of the given VASS is flat (i.e., without nested cycles). We obtain a family of VASS in dimension 3 whose shortest reachability witnessing runs are exponential, and we show that the reachability problem is NP-hard in dimension 7. These results resolve negatively questions that had been posed by the works of Blondin et al. in LICS 2015 and Englert et al. in LICS 2016, and contribute a first construction that distinguishes 3-dimensional flat VASS from 2-dimensional VASS. Our third result, by means of a novel family of products of integer fractions, shows that 4-dimensional VASS can have doubly exponentially long shortest reachability witnessing runs. The smallest dimension for which this was previously known is 14.
- 31 March 2020
- Published by Elsevier in Information and Computation
- Vol. 277, 104579
Preface