Streamability of nested word transductions

Autor: Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, Frédéric Servais

Publikováno v: Logical Methods in Computer Science, Vol Volume 15, Issue 2 (2019)

We consider the problem of evaluating in streaming (i.e., in a single left-to-right pass) a nested word transduction with a limited amount of memory. A transduction T is said to be height bounded memory (HBM) if it can be evaluated with a memory that

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

Visibly pushdown transducers

Autor: Jean-Marc Talbot, Emmanuel Filiot, Frédéric Servais, Pierre-Alain Reynier, Jean-François Raskin

Publikováno v: Journal of Computer and System Sciences
Journal of Computer and System Sciences, Elsevier, 2018, 97, pp.147-181. ⟨10.1016/j.jcss.2018.05.002⟩
Journal of Computer and System Sciences, 2018, 97, pp.147-181. ⟨10.1016/j.jcss.2018.05.002⟩

Visibly pushdown transducers ( VPT ) extend visibly pushdown automata (VPA) with outputs. They read nested words, i.e. finite words on a structured alphabet partitioned into call, return and internal symbols, and produce output words, which are not n

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0bff81a1770d4538024c283871fd22ce
https://doi.org/10.1016/j.jcss.2018.05.002

On the computation of the minimal coverability set of Petri nets

Autor: Frédéric Servais, Pierre-Alain Reynier

Publikováno v: Reachability Problems 13th International Conference, RP 2019, Brussels, Belgium, September 11–13, 2019, Proceedings
13th International Conference on Reachability Problems
13th International Conference on Reachability Problems, Sep 2019, Bruxelles, Belgium. ⟨10.1007/978-3-030-30806-3_13⟩
Lecture Notes in Computer Science ISBN: 9783030308056
RP

International audience; The verification of infinite-state systems is a challenging task. A prominent instance is reachability analysis of Petri nets, for which no efficient algorithm is known. The minimal coverability set of a Petri net can be under

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

XEvolve

Autor: Frédéric Servais, François Picalausa, Esteban Zimányi

Publikováno v: SAC

This paper presents XEvolve, a framework that unifies streaming validation of XML documents, and efficient testing of equivalence and inclusion of specifications for various XML schema languages. For these purposes, this framework relies on Visibly P

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::807cf2b9cf54ed8a433ef9616b1d8422
https://doi.org/10.1145/1982185.1982530

Minimal coverability set for Petri nets: Karp and Miller algorithm with pruning

Autor: Pierre-Alain Reynier, Frédéric Servais

Publikováno v: Petri Nets
Applications and Theory of Petri Nets ISBN: 9783642218330

This paper presents the Monotone-Pruning algorithm (MP) for computing the minimal coverability set of Petri nets. The original Karp and Miller algorithm (K&M) unfolds the reachability graph of a Petri net and uses acceleration on branches to ensure t

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6fd0b53d6a135cd4b895156ff3318751