Slides
- Orbit-finite linear programming
- The reachability problem for Petri nets
- Orbit-finite linear programming
- Frontiers of automatic analysis of concurrent systems
- Solvability of orbit-finite systems of linear equations
- Some recent advances in register automata
- Improved Ackermannian lower bound for the Petri nets reachability problem
- Lower bounds for reachability in VASS in fixed dimension
- Computation theory with atoms I
- Computation theory with atoms II
- The reachability problem for Petri nets is not elementary
- Timed pushdown automata and branching vector addition systems
- Homomorphism problems for FO definable structures
- Decidability border for Petri nets with data: WQO dichotomy conjecture
- Automata with timed atoms
- Reachability analysis of first-order definable pushdown automata
- Computation with atoms
- Turing machines over infinite alphabets
- Fast bisimulation-checking for normed context-free processes
Papers
(see also: DBLP entry; PubMed entry; Arxiv reports; Google scholar profile; other technical reports below; ORCID entry; Scopus entry)- A. Ghosh, P. Hofman, S. Lasota,
Orbit-finite linear programming.
Journal of the ACM, accepted.
[ PDF ] - Ł. Kamiński, S. Lasota,
Bi-reachability in Petri nets with data. CONCUR'24.
[ on-line version ] [ arXiv report ] - A. Ghosh, S. Lasota,
Equivariant ideals of polynomials. LICS'24.
[ on-line version ] [ arXiv report ] - W. Czerwiński, I. Jecker, S. Lasota, J. Leroux, Ł. Orlikowski,
New Lower Bounds for Reachability in Vector Addition Systems. FSTTCS'23.
[ on-line version ] [ arXiv report ] - A. Ghosh, P. Hofman, S. Lasota,
Orbit-finite linear programming. LICS'23.
LICS DISTINGUISHED PAPER
[ on-line version ] [ arXiv report ] - A. Ghosh, P. Hofman, S. Lasota,
Solvability of orbit-finite systems of linear equations. LICS'22.
[ on-line version ] [ arXiv report ] - L. Clemente, S. Lasota, R. Piórkowski,
Determinisability of register and timed automata. Logical Methods in Computer Science 18(2), 2022.
[ on-line version ] [ arXiv report ] - S. Lasota,
Improved Ackermannian lower bound for the Petri nets reachability problem. STACS'22.
[ on-line version ] [ arXiv report ] - S. Lasota, M. Pattathurajan,
Parikh images of register automata. FSTTCS'21.
[ on-line version ] - W. Czerwiński, S. Lasota, Ł. Orlikowski,
Improved lower bounds for reachability in vector addition systems. ICALP'21.
[ on-line version ] - P. Hofman, M. Juzepczuk, S. Lasota, M. Pattathurajan,
Parikh’s theorem for infinite alphabets. LICS'21.
[ arXiv report ] - B. Klin, S. Lasota, Sz. Toruńczyk,
Nondeterministic and co-Nondeterministic Implies Deterministic, for Data Languages. FOSSACS'21.
BEST PAPER AWARD
[ PDF ] - L. Clemente, S. Lasota,
Reachability relations of timed pushdown automata.
Journal of Computer and System Sciences 117, 2021.
[ on-line version ] [ arXiv report ] @Elsevier - M. Englert, P.Hofman, S. Lasota, R. Lazic, J. Leroux, J. Straszyński,
A lower bound for the coverability problem in acyclic pushdown VAS.
Information Processing Letters 167, 2021.
[ on-line version ] @Elsevier
- W. Czerwiński, S. Lasota, R. Lazic, J. Leroux, F. Mazowiecki,
The Reachability Problem for Petri Nets is Not Elementary.
Journal of the ACM 68(1), 2021.
[ on-line version ] [ PDF ] - L. Clemente, S. Lasota, R. Piórkowski,
Determinizability of one-clock timed automata. CONCUR'20.
[ on-line version ] [ arXiv report ] - W. Czerwiński, S. Lasota, R. Lazic, J. Leroux, F. Mazowiecki,
Reachability in fixed dimension vector addition systems with states. CONCUR'20.
[ on-line version ] [ arXiv report ] - L. Clemente, S. Lasota, R. Piórkowski,
Timed games and deterministic separability. ICALP'20.
[ on-line version ] [ arXiv report ] - S. Lasota, R. Piórkowski,
WQO dichotomy for 3-graphs.
Information and Computation 275, 2020.
[ on-line version ] [ arXiv report ] - K. Keshvardoost, B.Klin, S.Lasota, J.Ochremiak, Sz. Toruńczyk,
Definable isomorphism problem.
Logical Methods in Computer Science 15(4), 2019.
[ on-line version ] [ arXiv report ] - W. Czerwiński, S. Lasota, C. Löding, R. Piórkowski,
New Pumping Technique for 2-Dimensional VASS. MFCS'19.
[ on-line version ] [ arXiv report ] - W. Czerwiński, S. Lasota, R. Lazic, J. Leroux, F. Mazowiecki,
The Reachability Problem for Petri Nets is Not Elementary. STOC'19.
BEST PAPER AWARD
[ PDF ] [ arXiv report ] - L. Clemente, S. Lasota, R. Lazic, F. Mazowiecki,
Binary reachability of timed-register pushdown automata, and branching vector addition systems.
ACM Transactions on Computational Logic 20(3), 2019.
[ PDF ] - W. Czerwiński, S. Lasota,
Regular separability of one counter automata.
Logical Methods in Computer Science 15(2), 2019.
[ on-line version ] [ arXiv report ] - S. Lasota,
VASS reachability in three steps.
[ arXiv report ] - W. Czerwiński, S. Lasota, R. Meyer, S. Muskalla, K Narayan Kumar, P. Saivasan,
Regular Separability of Well Structured Transition Systems. CONCUR'18.
[ on-line version ] [ arXiv report ] - P. Hofman, S. Lasota,
Linear Equations with Ordered Data. CONCUR'18.
[ on-line version ] [ arXiv report ] - L. Clemente, S. Lasota,
Binary reachability of timed pushdown automata via quantifier elimination and cyclic order atoms. ICALP'18.
[ on-line version ] [ arXiv report ] - S. Lasota, R. Piórkowski,
WQO dichotomy for 3-graphs. FOSSACS'18.
[ PDF ] [ arXiv report ] - L. Clemente, W. Czerwiński, S. Lasota, C. Paperman,
Regular Separability of Parikh Automata. ICALP'17.
[ PDF ] [ arXiv report ] - W. Czerwiński, S. Lasota,
Regular separability of one counter automata. LICS'17.
[ PDF ] [ arXiv report ] - L. Clemente, S. Lasota, R. Lazic, F. Mazowiecki,
Timed pushdown automata and branching vector addition systems. LICS'17.
[ PDF ] - L. Clemente, W. Czerwiński, S. Lasota, C. Paperman,
Separability of Reachability Sets of Vector Addition Systems. STACS'17.
[ PDF ] [ arXiv report ] - B. Klin, S. Lasota, J. Ochremiak, Sz. Toruńczyk,
Homomorphism problems for first-order definable structures. FSTTCS'16.
[ PDF ] - S. Lasota,
Equivariant algorithms for constraint satisfaction problems over coset templates.
Information Processing Letters 118, 2017.
[ arXiv report ] [ on-line version ] @Elsevier
- S. Lasota,
Decidability border for Petri nets with data: WQO dichotomy conjecture.
Petri Nets'16.
[ PDF ] - P. Hofman, S. Lasota, R. Mayr, P. Totzke,
Simulation Problems Over One-Counter Nets.
Logical Methods in Computer Science 12(1), 2016.
[ BibTex entry ] [ arXiv report ] - Lasota, S., Poturalski, M.,
Undecidability of performance equivalence of Petri nets.
Theoretical Computer Science 655 (part B), 2016.
[ BibTex entry ] [ on-line version ] @Elsevier - P. Hofman, S. Lasota, R. Lazic, J. Leroux, S. Schmitz, P. Totzke,
Coverability Trees for Petri Nets with Unordered Data. FOSSACS'16.
[ PDF ] [ BibTex entry ] [ full version ] - L. Clemente, S. Lasota,
Reachability analysis of first-order definable pushdown systems. CSL'15.
[ PDF ] [ BibTex entry ] [ arXiv report ] - L. Clemente, S. Lasota,
Timed pushdown automata revisited. LICS'15.
[ PDF ] [ BibTex entry ] [ arXiv report ] - B. Klin, S. Lasota, J. Ochremiak, Sz. Toruńczyk,
Turing Machines with Atoms, Constraint Satisfaction Problems, and Descriptive Complexity. CSL/LICS'14.
[ PDF ] [ BibTex entry ] - G. Anielak, G. Jakacki, S. Lasota,
Incremental Test Case Generation Using Bounded Model Checking: an Application to Automatic Rating.
International Journal on Software Tools for Technology Transfer 17:339-349, 2015.
[ PDF ] [ BibTex entry ] [ on-line version ] - W. Czerwiński, P. Hofman, S. Lasota,
Decidability of bisimulation on normed commutative context-free processes with silent moves.
Theory of Computing Systems 55(1):136-169, 2014.
[ PDF ] [ BibTex entry ] [ on-line version ] - M. Bojańczyk, B. Klin, S. Lasota,
Automata theory in nominal sets.
Logical Methods in Computer Science 10 (3:4), 2014.
[ PDF ] [ BibTex entry ] [ on-line version ] - D. Figueira, P. Hofman, S. Lasota,
Relating timed and register automata.
Mathematical Structures in Computer Science 26(6), 2016.
[ BibTex entry ] [ on-line version ] @Cambridge University Press - P. Hofman, S. Lasota, R. Mayr, P. Totzke,
Simulation Over One-counter Nets is PSPACE-Complete. FSTTCS'13.
[ arXiv report ] [ BibTex entry ] - M. Bojańczyk, B. Klin, S. Lasota, Sz. Toruńczyk,
Turing machines with atoms. LICS'13.
[ PDF ] [ BibTex entry ] - A. Gambin, S. Lasota, M. Rybiński, Z. Szymańska,
Modelling the efficacy of hyperthermia treatment.
Journal of the Royal Society Interface, 10(88):20130527, 2013.
[ on-line version ] [ BibTex entry ] - W. Czerwiński, P. Hofman, S. Lasota,
Reachability problem for weak multi-pushdown automata.
Logical Methods in Computer Science 9 (3:13), 2013.
[ PDF ] [ BibTex entry ] - M. Bojańczyk, S. Lasota,
Fraenkel-Mostowski sets with non-homogeneous atoms. RP'12.
[ PDF ] [ BibTex entry ] - W. Czerwiński, S. Lasota,
Partially-commutative context-free languages. EXPRESS'12.
[ BibTex entry ] [ on-line version ] - W. Czerwiński, P. Hofman, S. Lasota,
Reachability problem for weak multi-pushdown automata. CONCUR'12.
[ PDF (full version) ] [ BibTex entry ] - M. Bojańczyk, S. Lasota,
A machine-independent characterization of timed languages. ICALP'12.
[ PDF ] [ PDF (full version)] [ BibTex entry ] - M. Bojańczyk, L. Braud, B. Klin, S. Lasota,
Towards nominal computation. POPL'12.
[ PDF ] [ BibTex entry ] - M. Bojańczyk, S. Lasota,
An extension of data automata that captures XPath.
Logical Methods in Computer Science 8 (1:5), 2012.
[ arXiv report ] [ BibTex entry ] [ on-line version ] - P. Banasik, A. Gambin, S. Lasota, M. Lula, M. Rybiński,
Tav4SB: integrating tools for analysis of kinetic models of biological systems.
BMC Systems Biology 6:25, 2012.
[ on-line version ] [ BibTex entry ] - M. Startek, S. Lasota, M. Sykulski, A. Bulak, L. Noe, G. Kucherov, A. Gambin,
Efficient alternatives to PSI-BLAST.
Bulletin of the Polish Academy of Sciences: Technical Sciences, 60(3):495-505, 2012.
[ PDF ] - W. Czerwiński, P. Hofman, S. Lasota,
Decidability of branching bisimulation on normed commutative context-free processes. CONCUR'11.
[ PDF (full version) ] [ BibTex entry ] @Springer-Verlag - W. Czerwiński, S. Froeschle, S. Lasota,
Partially-commutative context-free processes: expressibility and tractability.
Information and Computation 209:782-798, 2011.
[ BibTex entry ] [on-line version ] @Elsevier - M. Rybiński, M. Lula, S. Lasota, A. Gambin,
Tav4SB: grid environment for analysis of kinetic models of biological systems. ISBRA'11 Short Abstract.
[ PDF ] [ BibTex entry ] @Springer-Verlag - M. Bojańczyk, B. Klin, S. Lasota,
Automata with group actions. LICS'11.
[ PDF ] [ BibTex entry ] - A. Gambin, G. Kucherov, S. Lasota, L. Noe, M. Startek, M. Sykulski,
Subset seed extension to protein BLAST. Bioinformatics'11.
[ BibTex entry ] [ on-line version ] - W. Czerwiński, S. Lasota,
Fast equivalence-checking for normed context-free processes. FSTTCS'10.
[ PDF ] [ BibTex entry ] [ on-line version ] - D. Figueira, P. Hofman, S. Lasota,
Relating timed and register automata. EXPRESS'10.
[ PDF ] [ BibTex entry ] [ arXiv report ] - M. Bojańczyk, S. Lasota,
An extension of data automata that captures XPath. LICS'10.
[ PDF (full version) ] [ BibTex entry ] - S. Froeschle, P. Jancar, S. Lasota, Z.Sawa,
Non-Interleaving Bisimulation Equivalences on Basic Parallel Processes.
Information and Computation 208(1):42-62, 2010.
[ BibTex entry ] [ on-line version ] @Elsevier
- S. Lasota,
EXPSPACE lower bounds for the simulation preorder between a communication-free Petri net and a finite-state system.
Information Processing Letters 109:850-855, 2009.
[ PDF ] [ BibTex entry ] [ on-line version ] @Elsevier
- E. Furletova, A. Gambin, G. Kucherov, S. Lasota, L. Noe, M. Roytberg, E. Szczurek,
On subset seeds for protein alignment.
IEEE/ACM Transactions on Computational Biology and Bioinformatics 6(3):483-494, 2009.
[ BibTex entry ] [ on-line version ] @IEEE - W. Czerwiński, S. Froeschle, S. Lasota,
Partially-commutative context-free processes. CONCUR'09.
[ PDF ] [ BibTex entry ] [ slides (PDF) ] @Springer-Verlag - Froeschle, S., Lasota, S.
Normed Processes, Unique Decomposition, and Complexity of Bisimulation Equivalences. INFINITY'06, ENTCS 239, 2009.
[ PDF ] [ BibTex entry ] [ on-line version ] @Elsevier - Goubault-Larrecq, J., Lasota, S., Nowak, D.
Logical Relations for Monadic Types.
Mathematical Structures in Computer Science 18(6):1169-1217, 2008.
[ BibTex entry ] [ on-line version ] @Cambridge University Press - Lasota, S., Walukiewicz, I.
Alternating Timed Automata.
ACM Transactions on Computational Logic 9(2), Article 10, 2008.
[ PDF ] [ BibTex entry ] [ on-line version ] @ACM - E. Furletova, A. Gambin, G. Kucherov, S. Lasota, L. Noe, M. Roytberg, E. Szczurek.
Efficient seeding techniques for protein similarity search.
Bioinformatics Research and Development (BIRD'08), Communications in Computer and Information Science.
[ PDF ] [ BibTex entry ] [ on-line version ] @Springer-Verlag - Grzebelus, D., Lasota, S., Gambin, T., Kucherov, G., Gambin A.
Diversity and structure of PIF/Harbinger-like elements in the genome of Medicago truncatula.
BMC Genomics 8:409, 2007.
[ on-line version ] @BioMed Central Ltd - Froeschle, S., Lasota, S.
Causality Versus True-Concurrency.
Theoretical Computer Science 386:169-187, 2007.
[ BibTex entry ] [ on-line version ] @Elsevier - S. Lasota, D. Nowak and Y. Zhang.
On completeness of logical relations for monadic types. ASIAN'06.
[ PDF ] [ BibTex entry ] [ on-line version ] @Springer-Verlag -
Lasota, S.
Decidability of Performance Equivalence for Basic Parallel Processes.
Theoretical Computer Science 360:172-192, 2006.
[ BibTex entry ] @Elsevier -
Gambin A., Lasota, S., Rutkowski, M.
Analyzing stationary states of gene regulatory network using Petri nets.
In Silico Biology 6, 0010, 2006.
[ BibTex entry ] [ on-line version ] - Lasota, S., Rytter, W.
Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes. MFCS'06.
[ gzipped postscript ] [ PDF ] [ BibTex entry ] [ on-line version ] @Springer-Verlag - Froeschle, S., Lasota, S.
Causality Versus True-Concurrency. EXPRESS'05, ENTCS 154(3), 2006.
[ gzipped postscript ] [ BibTex entry ] [ on-line version ] @Elsevier - Froeschle, S., Lasota, S.
Decomposition and Complexity of Hereditary History Preserving Bisimulation on BPP. CONCUR'05.
[ gzipped postscript ] [ BibTex entry ] @Springer-Verlag - Lasota, S., Walukiewicz, I.
Alternating Timed Automata. FOSSACS'05.
[ gzipped postscript ] [ BibTex entry ] @Springer-Verlag - Koronacki, J., Lasota, S., Niemiro, W.
Position Emission Tomography by Markov Chain Monte Carlo with Auxiliary Variables.
Pattern Recognition 38(2):241-250, 2005.
[ BibTex entry ] [ on-line version ] @Elsevier - Gambin, A., Hidders, J., Kwaśnikowska, N., Lasota, S., Sroka, J., Tyszkiewicz, J., Van den Bussche, J.
Well Constructed Workflows in Bioinformatics. Workshop on Database Issues in Biological Databases (DBiBD 2005).
- Goubault-Larrecq, J., Lasota, S., Nowak, D., Zhang, Y.
Complete lax logical relations for cryptographic lambda-calculi. CSL'04.
[ gzipped postscript ] [ BibTex entry ] @Springer-Verlag - Lasota, S.
A Polynomial-Time Algorithm for Deciding True Concurrency Equivalences of Basic Parallel Processes. MFCS'03.
[ gzipped postscript ] [ gzipped postscript of the full version ] [ BibTex entry ] @Springer-Verlag -
Lasota, S., Niemiro, W.
A Version of the Swandsen-Wang Algorithm for Restoration of Images Degraded by Poisson Noise.
Pattern Recognition 36(4):931-941, 2003.
[ BibTex entry ] [ on-line version ] @Elsevier - Goubault-Larrecq, J., Lasota, S., Nowak, D.
Logical Relations for Monadic Types. CSL'02.
[ gzipped postscript ] [ BibTex entry ] @Springer-Verlag - Lasota, S.
Decidability of strong bisimilarity for timed BPP. CONCUR'02.
[ gzipped postscript ] [ BibTex entry ] @Springer-Verlag - Gambin, A., Lasota, S., Szklarczyk, R., Tiuryn, J., Tyszkiewicz, J.
Contextual Alignment of Biological Sequences.
Proc. ECCB'02, Bioinformatics 18:116-127, Oxford University Press, 2002.
[ gzipped postscript ] [ BibTex entry ] -
Lasota, S.
Coalgebra morphisms subsume open maps.
Theoretical Computer Science 280:123-135, 2002.
[ BibTex entry ] [ on-line version ] @Elsevier - Dietzfelbinger, M., Gambin, A., Lasota, S. On Different Models for Packet Flow in Multistage Interconnection Networks. Fundamenta Informaticae 46(4):287-314, 2001.
- Lasota, S.
Behavioural constructor implementation for regular algebras. LPAR'2000.
[ gzipped postscript ] @Springer-Verlag - Lasota, S.
Finitary observations in regular algebras. SOFSEM '2000.
[ gzipped postscript ] @Springer-Verlag - Lasota, S.
Coalgebra morphisms subsume open maps (preliminary version). CMCS'99, volume 19 of ENTCS, 1999.
[ gzipped postscript ] - Lasota, S.
Weak Bisimilarity and Open Maps. SOFSEM '98.
[ gzipped postscript ] @Springer-Verlag - Lasota, S.
Partial-Congruence Factorization of Bisimilarity Induced by Open Maps. ICALP'98.
[ gzipped postscript of the full version ] @Springer-Verlag - Lasota, S.
Open Maps as a Bridge between Algebraic Observational Equivalence and Bisimilarity. WADT'97, 1998.
[ gzipped postscript of the full version ] @Springer-Verlag - Gambin, A., Lasota, S.
On the Semantics of Multistage Interconnnection Networks. SOFSEM'96.
[ gzipped postscript ] [ gzipped postscript of the full version ] @Springer-Verlag
Technical reports
- P. Hofman, S. Lasota, R. Lazić, J. Leroux, S. Schmitz, P. Totzke,
Coverability Trees for Petri Nets with Unordered Data.
HAL report hal-01252674, 2016. - Froeschle, S., Lasota, S.
Decomposition and Complexity of Hereditary History Preserving Bisimulation on BPP.
The full version.
Technical Report 280, Institute of Informatics, Warsaw University, 2005.
[ postscript ] - Jean Goubault-Larrecq, S. Lasota, David Nowak
Logical Relations for Monadic Types. The full version.
Research Report LSV-04-13, Lab. Specification and Verification, ENS Cachan, France, June 2004.
[ postscript ] - Jean Goubault-Larrecq, S. Lasota, David Nowak, Yu Zhang
Complete lax logical relations for cryptographic lambda-calculi.
Research Report LSV-04-4, Lab. Specification and Verification, ENS Cachan, France, February 2004.
[ postscript ] - S. Lasota.
A polynomial-time algorithm for deciding true concurrency equivalences of Basic Parallel Processes.
Research Report LSV-02-13, Lab. Specification and Verification, ENS Cachan, France, September 2002.
[ gzipped postscript ] - Koronacki, J., Lasota, S., Niemiro, W.
Position Emission Tomography by Markov Chain Monte Carlo with Auxiliary Variables: A Basic Algorithm.
Technical Report 884 IPI PAN, 1999. -
Dietzfelbinger, M., Gambin, A., Lasota, S.
On Different Models for Packet Flow in Multistage Interconnection Networks.
Technical report 97-11(248), Institute of Informatics, Warsaw University, 1997.
[ gzipped postscript ] -
Lasota, S.
Open Maps as a Bridge between Algebraic Observational Equivalence and
Bisimilarity.
The full version.
Technical report 97-12(249), Institute of Informatics, Warsaw University, 1997.
[ gzipped postscript ]