Výsledky vyhledávání - "Sylvain Schmitz"

Akademický článek

Autor: Christoph Haase, Sylvain Schmitz, Philippe Schnoebelen

Publikováno v: Logical Methods in Computer Science, Vol Volume 10, Issue 4 (2014)

We introduce Priority Channel Systems, a new class of channel systems where messages carry a numeric priority and where higher-priority messages can supersede lower-priority messages preceding them in the fifo communication buffers. The decidability

Externí odkaz: https://doaj.org/article/da04677659a544c7b310233e732e89a9

Zobrazit plný text záznamu

On Ordinal Invariants in Well Quasi Orders and Finite Antichain Orders

Autor: Sylvain Schmitz, Mirna Dzamonja, Philippe Schnoebelen

Publikováno v: Well-Quasi Orders in Computation, Logic, Language and Reasoning
Peter M. Schuster; Monika Seisenberger; Andreas Weiermann. Well-Quasi Orders in Computation, Logic, Language and Reasoning, 53, Springer, 2020, Trends in Logic, ⟨10.1007/978-3-030-30229-0_2⟩
Trends in Logic ISBN: 9783030302283

International audience; We investigate the ordinal invariants height, length, and width of well quasi orders (WQO), with particular emphasis on width, an invariant of interest for the larger class of orders with finite antichain condition (FAC). We s

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8cd143e483c5738db24b102d2d7ba3f3
https://halshs.archives-ouvertes.fr/halshs-01625981/document

Zobrazit plný text záznamu

Bisimulation Equivalence of First-Order Grammars is ACKERMANN-Complete

Autor: Petr Jancar, Sylvain Schmitz

Publikováno v: LICS 2019, 34th Annual ACM/IEEE Symposium on Logic in Computer Science
LICS 2019, 34th Annual ACM/IEEE Symposium on Logic in Computer Science, Jun 2019, Vancouver, Canada. pp.1--12, ⟨10.1109/LICS.2019.8785848⟩
LICS

International audience; Checking whether two pushdown automata with restricted silent actions are weakly bisimilar was shown decidable by Sénizergues (1998, 2005). We provide the first known complexity upper bound for this famous problem, in the equ

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c3cb0df2dd8db69038ff6a4d31c4a1d6
https://hal.archives-ouvertes.fr/hal-02267529

Zobrazit plný text záznamu

Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension

Autor: Sylvain Schmitz, Jérôme Leroux

International audience; The reachability problem in vector addition systems is a central question, not only for the static verification of these systems, but also for many inter-reducible decision problems occurring in various fields. The currently b

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6298486ace3dc7070a95ceee077d54ea
http://arxiv.org/abs/1903.08575

Zobrazit plný text záznamu

Decidable XPath Fragments in the Real World

Autor: Anthony Lick, Sylvain Schmitz, David Baelde

Publikováno v: 38th ACM Symposium on Principles of Database Systems (PODS'19)
38th ACM Symposium on Principles of Database Systems (PODS'19), 2019, Amsterdam, Netherlands. ⟨10.1145/3294052.3319685⟩
38th ACM Symposium on Principles of Database Systems (PODS'19), Jun 2019, Amsterdam, Netherlands. ⟨10.1145/3294052.3319685⟩
PODS

International audience; XPath is arguably the most popular query language for selecting elements in XML documents. Besides query evaluation, query satisfiability and containment are the main computational problems for XPath; they are useful, for inst

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::de6dd9086c5818fedf31b36033b2afc8
https://hal.inria.fr/hal-01852475

Zobrazit plný text záznamu

Coverability Is Undecidable in One-Dimensional Pushdown Vector Addition Systems with Resets

Autor: Georg Zetzsche, Sylvain Schmitz

Publikováno v: 13th International Conference on Reachability Problems (RP 2019)
13th International Conference on Reachability Problems (RP 2019), 2019, Brussels, Belgium. pp.193--201, ⟨10.1007/978-3-030-30806-3_15⟩
Lecture Notes in Computer Science ISBN: 9783030308056
RP

We consider the model of pushdown vector addition systems with resets. These consist of vector addition systems that have access to a pushdown stack and have instructions to reset counters. For this model, we study the coverability problem. In the ab

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b254e6f99ad971448ab4fde95ec694a1
https://hal.archives-ouvertes.fr/hal-03440052

Zobrazit plný text záznamu

Elektronická kniha

Reachability Problems : 14th International Conference, RP 2020, Paris, France, October 19–21, 2020, Proceedings

Autor: Sylvain Schmitz, Igor Potapov

This book constitutes the refereed proceedings of the 14th International Conference on Reachability Problems, RP 2020, held in Paris, France in October 2020.The 8 full papers presented were carefully reviewed and selected from 25 submissions. In addi

Zobrazit plný text záznamu

The complexity of reachability in vector addition systems

Autor: Sylvain Schmitz

Publikováno v: ACM SIGLOG News. 3:4-21

The program of the 30th Symposium on Logic in Computer Science held in 2015 in Kyoto included two contributions on the computational complexity of the reachability problem for vector addition systems: Blondin, Finkel, Göller, Haase, and McKenzie [20

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::a81b50c01aea9de1c008a066aa7baad4
https://doi.org/10.1145/2893582.2893585

Zobrazit plný text záznamu

Nonelementary Complexities for Branching VASS, MELL, and Extensions

Autor: Ranko Lazić, Sylvain Schmitz

Publikováno v: ACM Transactions on Computational Logic
ACM Transactions on Computational Logic, Association for Computing Machinery, 2015, 16 (3:20), pp.1--30. ⟨10.1145/2733375⟩
CSL-LICS
Joint meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science
Joint meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science, Jul 2014, Vienna, Austria. pp.61:1--61:1, ⟨10.1145/2603088.2603129⟩
ACM Transactions on Computational Logic, 2015, 16 (3:20), pp.1--30. ⟨10.1145/2733375⟩

We study the complexity of reachability problems on branching extensions of vector addition systems, which allows us to derive new non-elementary complexity bounds for fragments and variants of propositional linear logic. We show that provability in

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9d47179e80b45a5ce9a621cc9fde5bbb
https://doi.org/10.1145/2733375

Zobrazit plný text záznamu

The Complexity of Diagnosability and Opacity Verification for Petri Nets

Autor: Béatrice Bérard, Stefan Haar, Sylvain Schmitz, Stefan Schwoon

Publikováno v: Petri nets 2017-38th International Conference on Applications and Theory of Petri Nets and Concurrency
Petri nets 2017-38th International Conference on Applications and Theory of Petri Nets and Concurrency, Jun 2017, Zaragoza, Spain. pp.200--220, ⟨10.1007/978-3-319-57861-3_13⟩
Fundamenta Informaticae
Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2018, 161 (4), pp.317--349. ⟨10.3233/FI-2018-1706⟩
Fundamenta Informaticae, 2018, 161 (4), pp.317--349. ⟨10.3233/FI-2018-1706⟩
Application and Theory of Petri Nets and Concurrency ISBN: 9783319578606
Petri Nets

International audience; Diagnosability and opacity are two well-studied problems in discrete-event systems. We revisit these two problems with respect to expressiveness and complexity issues. We first relate different notions of diagnosability and op

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::de289f3c82bfbe80ba598c6d7f06b1c8
https://hal.inria.fr/hal-01484476v2/document

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání