M. Faouzi, A. , and P. Habermehl, On Yen's path logic for Petri nets, Int. J. Fund. Comput. Sci, vol.22, issue.4, pp.783-79910, 2011.

K. Bimbó, The decidability of the intensional fragment of classical linear logic, Theoretical Computer Science, vol.597, pp.1-17, 2015.
DOI : 10.1016/j.tcs.2015.06.019

M. Blockelet and S. Schmitz, Model Checking Coverability Graphs of Vector Addition Systems, Proc. MFCS 2011, pp.108-119, 2011.
DOI : 10.1007/978-3-642-22993-0_13

URL : https://hal.archives-ouvertes.fr/hal-00600077

M. Blondin, A. Finkel, S. Göller, C. Haase, and P. Mckenzie, Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-Complete, 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, pp.32-43, 2015.
DOI : 10.1109/LICS.2015.14

M. Blondin, A. Finkel, C. Haase, and S. Haddad, Approaching the Coverability Problem Continuously, Proc. TACAS 2016 (Lect. Notes in Comput. Sci, 2016.
DOI : 10.1007/978-3-662-49674-9_28

URL : https://hal.archives-ouvertes.fr/hal-01408044

M. Bojá-nczyk, Some open problems in automata and logic, ACM SIGLOG News, vol.1, issue.2, pp.3-12, 2014.

M. Bojá-nczyk, C. David, A. Muscholl, T. Schwentick, and L. Segoufin, Two-variable logic on data words, ACM Trans. Comput. Logic, vol.12, issue.4, pp.27-28, 2011.

M. Bojá-nczyk, A. Muscholl, T. Schwentick, and L. Segoufin, Two-variable logic on data trees and XML reasoning, Journal of the ACM, vol.56, issue.3, pp.1-48, 2009.
DOI : 10.1145/1516512.1516515

R. Bonnet, Theory of Well-Structured Transition Systems and Extended Vector-Addition Systems http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/bonnet-phd13.pdf Wilfried Buchholz, E. Adam Cichó n, and Andreas Weiermann. 1994. A uniform approach to fundamental sequences and hierarchies, Thèse de doctorat. ENS Cachan, pp.273-286, 1994.

A. Cichó-n and E. T. Bittar, Ordinal recursive bounds for Higman's Theorem. Theor, 1998.

T. Colcombet and A. Manuel, Generalized data automata and fixpoint logic, Proc. FSTTCS 2014 (Leibniz Int. Proc. Inf.), 2014.

J. Courtois and S. Schmitz, Alternating Vector Addition Systems with States, Proc. MFCS 2014, pp.220-231, 2014.
DOI : 10.1007/978-3-662-44522-8_19

URL : https://hal.archives-ouvertes.fr/hal-00980878

S. Crespi-reghizzi and D. Mandrioli, Petri nets and szilard languages, Information and Control, vol.33, issue.2, pp.177-19210, 1977.
DOI : 10.1016/S0019-9958(77)90558-7

P. De-groote, B. Guillaume, and S. Salvati, Vector addition tree automata, Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science, 2004., pp.64-7351, 2004.
DOI : 10.1109/LICS.2004.1319601

N. Decker, P. Habermehl, M. Leucker, and D. Thoma, Ordered Navigation on Multi-attributed Data??Words, Proc. Concur 2014, pp.497-511, 2014.
DOI : 10.1007/978-3-662-44584-6_34

P. Degano, J. Meseguer, and U. Montanari, Axiomatizing net computations and processes, [1989] Proceedings. Fourth Annual Symposium on Logic in Computer Science, p.39172, 1989.
DOI : 10.1109/LICS.1989.39172

S. Demri, On selective unboundedness of VASS, Journal of Computer and System Sciences, vol.79, issue.5, pp.689-713, 2013.
DOI : 10.1016/j.jcss.2013.01.014

S. Demri, D. Figueira, and M. Praveen, Reasoning about data repetitions with counter systems, Proc. LICS 2013, pp.33-42, 2013.

S. Demri and R. Gascon, The Effects of Bounding Syntactic Resources on Presburger LTL, Journal of Logic and Computation, vol.19, issue.6, pp.1541-1575, 2009.
DOI : 10.1093/logcom/exp037

N. Dershowitz and Z. Manna, Proving termination with multiset orderings, Communications of the ACM, vol.22, issue.8, pp.465-476, 1979.
DOI : 10.1145/359138.359142

J. Dimino, F. Jacquemard, and L. Segoufin, FO 2 (<, +1, ?) on data trees, data tree automata and branching vector addition systems, 2015.
URL : https://hal.archives-ouvertes.fr/hal-00769249

U. Engberg and G. Winskel, Completeness results for linear logic on Petri nets, Annals of Pure and Applied Logic, vol.86, issue.2, pp.101-13510, 1997.
DOI : 10.1016/S0168-0072(96)00024-3

J. Esparza, Decidability and complexity of Petri net problems ??? An introduction, Lect. Notes in Comput. Sci.), vol.1491, pp.374-428, 1998.
DOI : 10.1007/3-540-65306-6_20

J. Esparza, R. An-ledesma-garza, R. Majumdar, P. Meyer, and F. Niksic, An SMTbased approach to coverability analysis, Proc. CAV 2014 (Lect. Notes in Comput. Sci.), 2014.

. Springer, DOI:10, pp.603-619

J. Esparza and M. Nielsen, Decidability issues for Petri nets ? a survey, Bull. EATCS, vol.52, pp.244-262, 1994.

J. Fearnley and M. Jurdzí-nski, Reachability in two-clock timed automata is PSPACE-complete, 2015.

D. Figueira, S. Figueira, S. Schmitz, and P. Schnoebelen, Ackermannian and Primitive-Recursive Bounds with Dickson's Lemma, 2011 IEEE 26th Annual Symposium on Logic in Computer Science, pp.269-278, 2011.
DOI : 10.1109/LICS.2011.39

P. Ganty and R. Majumdar, Algorithmic verification of asynchronous programs, ACM Transactions on Programming Languages and Systems, vol.34, issue.1, pp.1-4810, 2012.
DOI : 10.1145/2160910.2160915

M. Steven, A. P. German, and . Sistla, Reasoning about systems with many processes, J. ACM, vol.39, issue.3, pp.675-73510, 1992.

J. Gischer, Shuffle languages, Petri nets, and context-sensitive grammars, Communications of the ACM, vol.24, issue.9, pp.597-605, 1981.
DOI : 10.1145/358746.358767

S. A. Greibach, Remarks on blind and partially blind one-way multicounter machines, Theoretical Computer Science, vol.7, issue.3, pp.311-32410, 1978.
DOI : 10.1016/0304-3975(78)90020-8

C. Haase and S. Kreutzer, Reachability in Succinct and Parametric One-Counter Automata, Proc. Concur, pp.369-383, 2009.
DOI : 10.1007/3-540-45061-0_53

H. T. Michel and . Hack, Decidability questions for Petri nets, 1975.

H. T. Michel and . Hack, Petri net languages Computation Structures Group Memo 124, 1975.

E. John, J. Hopcroft, and . Pansiot, On the reachability problem for 5-dimensional vector addition systems, Theor. Comput. Sci, vol.8, issue.79, pp.135-159, 1979.

R. R. Howell, L. E. Rosier, D. T. Huynh, and H. Yen, Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states, Theoretical Computer Science, vol.46, issue.86, pp.107-140, 1986.
DOI : 10.1016/0304-3975(86)90026-5

R. R. Howell, L. E. Rosier, and H. Yen, A taxonomy of fairness and temporal logic problems for Petri nets, Theoretical Computer Science, vol.82, issue.2, pp.341-372, 1991.
DOI : 10.1016/0304-3975(91)90228-T

P. Jan?ar, Decidability of a temporal logic problem for Petri nets, Theoretical Computer Science, vol.74, issue.1, pp.71-9310, 1990.
DOI : 10.1016/0304-3975(90)90006-4

A. Kaiser, D. Kroening, and T. Wahl, A Widening Approach to Multithreaded Program Verification, ACM Transactions on Programming Languages and Systems, vol.36, issue.4, p.2910, 1145.
DOI : 10.1145/2629608

M. I. Kanovich, Petri nets, Horn programs, linear logic and vector games, Ann. Pure Appl. Log, vol.75, issue.94, pp.1-2, 1995.
DOI : 10.1016/0168-0072(94)00060-g

URL : http://doi.org/10.1016/0168-0072(94)00060-g

A. Kara, T. Schwentick, and T. Zeume, Temporal logics on words with multiple data values, Proc. FSTTCS 2010 (Leibniz Int. Proc. Inf.), pp.481-492, 2010.

M. Richard, R. E. Karp, and . Miller, Parallel program schemata, J. Comput. Syst. Sci, vol.3, issue.269, pp.147-19510, 1969.

R. Kosaraju, Decidability of reachability in vector addition systems, Proc. STOC'82, pp.267-281, 1982.

J. Lambert, A structure to decide reachability in Petri nets, Theoretical Computer Science, vol.99, issue.1, pp.79-10410, 1992.
DOI : 10.1016/0304-3975(92)90173-D

R. Lazi´clazi´c, The reachability problem for vector addition systems with a stack is not elementary, Preprint, 2013.

R. Lazi´clazi´c, T. Newcomb, J. Ouaknine, A. W. Roscoe, and J. Worrell, Nets with tokens which carry data. Fund, Inform, vol.88, issue.3, pp.251-274, 2008.

R. Lazi´clazi´c and S. Schmitz, Non-elementary complexities for branching VASS, MELL, and extensions, 30 pages. DOI:10.1145, p.2733375, 2015.

J. Leroux, The general vector addition system reachability problem by Presburger inductive invariants, Logic. Meth. in Comput. Sci, vol.63, issue.3, pp.1-25, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00272667

J. Leroux, Vector addition system reachability problem: a short self-contained proof, Proc. POPL 2011, pp.307-316, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00599756

J. Leroux, Presburger Vector Addition Systems, 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science, pp.23-32
DOI : 10.1109/LICS.2013.7

URL : https://hal.archives-ouvertes.fr/hal-00780462

J. Leroux, Vector Addition System Reversible Reachability Problem, Logic. Meth. in Comput. Sci, vol.9, issue.51, pp.10-2168, 2013.
DOI : 10.1007/978-3-642-23217-6_22

URL : https://hal.archives-ouvertes.fr/hal-00599757

J. Leroux, M. Praveen, and G. Sutre, A Relational Trace Logic for Vector Addition Systems with Application to Context-Freeness, Proc. Concur 2013, pp.137-151, 2013.
DOI : 10.1007/978-3-642-40184-8_11

URL : https://hal.archives-ouvertes.fr/hal-00851915

J. Leroux and S. Schmitz, Demystifying Reachability in Vector Addition Systems, 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, pp.56-67, 2015.
DOI : 10.1109/LICS.2015.16

URL : https://hal.archives-ouvertes.fr/hal-01168388

J. Leroux and G. Sutre, On Flatness for 2-Dimensional Vector Addition Systems with States, Proc. Concur, pp.402-416, 2004.
DOI : 10.1137/0213029

R. J. Lipton, The reachability problem requires exponential space, 1976.

H. Martin, S. S. Löb, and . Wainer, Hierarchies of number-theoretic functions. I. Arch, Math. Log, vol.13, pp.1-2, 1970.

A. Irina, P. Lomazova, and . Schnoebelen, Some decidability results for nested Petri nets, Proc. PSI'99, pp.208-220, 2000.

E. W. Mayr, An algorithm for the general Petri net reachability problem, Proc. STOC'81, pp.238-246, 1981.

R. Mayr, Process rewrite systems, Inform. and Comput, vol.156, pp.1-2, 2000.
DOI : 10.1006/inco.1999.2826

URL : http://doi.org/10.1006/inco.1999.2826

R. Meyer, A theory of structural stationarity in the pi-calculus. Acta Inf DOI:10.1007/s00236-009-0091-x Horst M ¨ uller. 1985. The reachability problem for VAS. In Advances in Petri Nets 1984, Lect. Notes in Comput. Sci, vol.46, issue.188, pp.87-137, 2009.

M. Nielsen, G. Plotkin, and G. Winskel, Petri nets, event structures and domains, part I, Theoretical Computer Science, vol.13, issue.1, pp.85-108, 1981.
DOI : 10.1016/0304-3975(81)90112-2

URL : http://doi.org/10.1016/0304-3975(81)90112-2

A. Carl and . Petri, Kommunikation mit Automaten. Ph.D. Dissertation, 1962.

C. Rackoff, The covering and boundedness problems for vector addition systems, Theoretical Computer Science, vol.6, issue.2, pp.223-23110, 1978.
DOI : 10.1016/0304-3975(78)90036-1

O. Rambow, Multiset-valued linear index grammars, Proceedings of the 32nd annual meeting on Association for Computational Linguistics -, pp.263-270, 1994.
DOI : 10.3115/981732.981768

URL : http://arxiv.org/pdf/cmp-lg/9406009v1.pdf

K. Reinhardt, Reachability in Petri Nets with Inhibitor Arcs, Proc. RP, 2008.
DOI : 10.1016/j.entcs.2008.12.042

E. Render and M. Kambites, Rational subsets of polycyclic monoids and valence automata, Information and Computation, vol.207, issue.11, pp.1329-1339, 2009.
DOI : 10.1016/j.ic.2009.02.012

C. Reutenauer, The mathematics of Petri nets, 1990.

F. Rosa-velardo and M. Martos-salgado, Multiset rewriting for the verification of depth-bounded processes with name binding, Information and Computation, vol.215, pp.68-87, 2012.
DOI : 10.1016/j.ic.2012.03.004

E. Louis, . Rosier, and . Hsu-chun-yen, A multiparameter analysis of the boundedness problem for vector addition systems, J. Comput. Syst. Sci, vol.32, issue.186, pp.105-135, 1986.

S. George, R. L. Sacerdote, and . Tenney, The decidability of the reachability problem for vector addition systems, Proc. STOC'77, pp.61-7610, 1977.

S. Schmitz, On the computational complexity of dominance links in grammatical formalisms, Proc. ACL 2010, pp.514-524, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00482396

S. Schmitz, Complexity Bounds for Ordinal-Based Termination, Proc. RP 2014, pp.1-19, 2014.
DOI : 10.1007/978-3-319-11439-2_1

URL : https://hal.archives-ouvertes.fr/hal-01076701

S. Schmitz, Complexity Hierarchies beyond Elementary, ACM Transactions on Computation Theory, vol.8, issue.1, pp.10-1145, 2016.
DOI : 10.1145/2858784

URL : https://hal.archives-ouvertes.fr/hal-01267354