Zobrazeno 1 - 10
of 70
pro vyhledávání: '"Jérôme, Leroux"'
Autor:
Frank, Drewes, Jérôme, Leroux
Publikováno v:
Logical Methods in Computer Science, Volume 11, Issue 4 (December 22, 2015) lmcs:1616
A Petri net is structurally cyclic if every configuration is reachable from itself in one or more steps. We show that structural cyclicity is decidable in deterministic polynomial time. For this, we adapt the Kosaraju's approach for the general reach
Externí odkaz:
http://arxiv.org/abs/1510.08331
Autor:
jerome, leroux
Publikováno v:
Logical Methods in Computer Science, Volume 6, Issue 3 (September 9, 2010) lmcs:1024
The reachability problem for Vector Addition Systems (VASs) is a central problem of net theory. The general problem is known to be decidable by algorithms exclusively based on the classical Kosaraju-Lambert-Mayr-Sacerdote-Tenney decomposition. This d
Externí odkaz:
http://arxiv.org/abs/1009.1076
Autor:
Jérôme Leroux
Population protocols are a model of computation in which an arbitrary number of anonymous finite-memory agents are interacting in order to decide by stable consensus a predicate. In this paper, we focus on the counting predicates that asks, given an
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2db2756eb42891420bb4a0300e71188f
http://arxiv.org/abs/2109.15171
http://arxiv.org/abs/2109.15171
Autor:
Jérôme Leroux
Publikováno v:
Application and Theory of Petri Nets and Concurrency
Application and Theory of Petri Nets and Concurrency-42nd International Conference, {PETRI} {NETS} 2021
Application and Theory of Petri Nets and Concurrency-42nd International Conference, 2021, Jun 2021, Virtual Event, France. ⟨10.1007/978-3-030-76983-3_2⟩
Application and Theory of Petri Nets and Concurrency ISBN: 9783030769826
Petri Nets
Application and Theory of Petri Nets and Concurrency-42nd International Conference, {PETRI} {NETS} 2021
Application and Theory of Petri Nets and Concurrency-42nd International Conference, 2021, Jun 2021, Virtual Event, France. ⟨10.1007/978-3-030-76983-3_2⟩
Application and Theory of Petri Nets and Concurrency ISBN: 9783030769826
Petri Nets
International audience; Vector addition systems with states (VASS for short), or equivalently Petri nets are one of the most popular formal methods for the representation and the analysis of parallel processes. The central algorithmic problem is reac
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4679535103ca02db3d1e2780c253a636
https://hal.archives-ouvertes.fr/hal-03436231
https://hal.archives-ouvertes.fr/hal-03436231
Publikováno v:
International Symposium on Games, Automata, Logics, and Formal Verification, GandALF
International Symposium on Games, Automata, Logics, and Formal Verification, GandALF, 2021, NA, Italy
GandALF
International Symposium on Games, Automata, Logics, and Formal Verification, GandALF, 2021, NA, Italy
GandALF
The notion of separating automata was introduced by Bojanczyk and Czerwinski for understanding the first quasipolynomial time algorithm for parity games. In this paper we show that separating automata is a powerful tool for constructing algorithms so
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5d4a8014a3538dc21c21af605a9abf68
https://hal.archives-ouvertes.fr/hal-03410670
https://hal.archives-ouvertes.fr/hal-03410670
Autor:
Jérôme Leroux
Publikováno v:
Logical Methods in Computer Science, Vol Volume 9, Issue 1 (2013)
The reachability problem for vector addition systems is a central problem of net theory. This problem is known to be decidable but the complexity is still unknown. Whereas the problem is EXPSPACE-hard, no elementary upper bounds complexity are known.
Externí odkaz:
https://doaj.org/article/00b69258672340448d2b7bb82951cfeb
Publikováno v:
LICS
LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science
LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Jul 2020, Saarbrücken, Germany. pp.676-688
LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science
LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Jul 2020, Saarbrücken, Germany. pp.676-688
The termination complexity of a given VASS is a function L assigning to every n the length of the longest non-terminating computation initiated in a configuration with all counters bounded by n. We show that for every VASS with demonic nondeterminism
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::535974488861934c2463068239639c4a
https://hal.archives-ouvertes.fr/hal-03052592
https://hal.archives-ouvertes.fr/hal-03052592
Publikováno v:
Logical Methods in Computer Science, Vol Volume 8, Issue 3 (2012)
The reachability analysis of recursive programs that communicate asynchronously over reliable FIFO channels calls for restrictions to ensure decidability. Our first result characterizes communication topologies with a decidable reachability problem r
Externí odkaz:
https://doaj.org/article/a539d43393d14da4abdf4428503e967f
Publikováno v:
Logical Methods in Computer Science, Vol Volume 8, Issue 2 (2012)
We design a variation of the Karp-Miller algorithm to compute, in a forward manner, a finite representation of the cover (i.e., the downward closure of the reachability set) of a vector addition system with one zero-test. This algorithm yields decisi
Externí odkaz:
https://doaj.org/article/96d85c86d0ea476494c14d3533919bea
Publikováno v:
Proceedings of the 51st Annual {ACM} {SIGACT} Symposium on Theory of Computing, {STOC} 2019, Phoenix, AZ, USA, June 23-26, 2019
Proceedings of the 51st Annual Symposium on Theory of Computing, 2019, Phoenix, AZ, USA, June 23-26, 2019, Jun 2019, Phoenix, United States. pp.24-33, ⟨10.1145/3313276.3316369⟩
JACM
Journal of the ACM (JACM)
Journal of the ACM (JACM), Association for Computing Machinery, 2021, 68 (1), pp.7. ⟨10.1145/3422822⟩
STOC
Proceedings of the 51st Annual Symposium on Theory of Computing, 2019, Phoenix, AZ, USA, June 23-26, 2019, Jun 2019, Phoenix, United States. pp.24-33, ⟨10.1145/3313276.3316369⟩
JACM
Journal of the ACM (JACM)
Journal of the ACM (JACM), Association for Computing Machinery, 2021, 68 (1), pp.7. ⟨10.1145/3422822⟩
STOC
Petri nets, also known as vector addition systems, are a long established model of concurrency with extensive applications in modelling and analysis of hardware, software and database systems, as well as chemical, biological and business processes. T
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1b102e033c4748b2b8989c8b54f5b8ae
https://hal.archives-ouvertes.fr/hal-02390629
https://hal.archives-ouvertes.fr/hal-02390629