×

zbMATH — the first resource for mathematics

Nonelementary complexities for branching VASS, MELL, and extensions. (English) Zbl 1354.68128

MSC:
68Q25 Analysis of algorithms and problem complexity
03F52 Proof-theoretic aspects of linear logic and other substructural logics
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Parosh Aziz Abdulla, Richard Mayr, Arnaud Sangnier, and Jeremy Sproston. 2013. Solving parity games on integer vectors. In Proc. Concur 2013. Lect. Notes in Comput. Sci., Vol. 8052. Springer, 106–120. DOI:10.1007/978-3-642-40184-8_9 · Zbl 1390.68452
[2] Andrea Asperti and Luca Roversi. 2002. Intuitionistic light affine logic. ACM Trans. Comput. Logic 3, 1 (2002), 137–175. DOI:10.1145/504077.504081 · Zbl 1365.03040 · doi:10.1145/504077.504081
[3] Mikołaj Bojańczyk, Anca Muscholl, Thomas Schwentick, and Luc Segoufin. 2009. Two-variable logic on data trees and XML reasoning. J. ACM 56, 3 (2009), 1–48. DOI:10.1145/1516512.1516515 · Zbl 1325.68078 · doi:10.1145/1516512.1516515
[4] Ahmed Bouajjani and Michael Emmi. 2013. Analysis of recursively parallel programs. ACM Trans. Prog. Lang. Syst. 35, 3 (2013), 10:1–10:49. DOI:10.1145/2518188 · Zbl 1321.68184 · doi:10.1145/2518188
[5] Tomáš Brázdil, Petr Jančar, and Antonín Kučera. 2010. Reachability games on extended vector addition systems with states. In Proc. ICALP 2010. Lect. Notes in Comput. Sci., Vol. 6199. Springer, 478–489. DOI:10.1007/978-3-642-14162-1_40
[6] Ashok K. Chandra, Dexter C. Kozen, and Larry J. Stockmeyer. 1981. Alternation. J. ACM 28, 1 (1981), 114–133. DOI:10.1145/322234.322243 · Zbl 0473.68043 · doi:10.1145/322234.322243
[7] Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, and Jean-François Raskin. 2010. Generalized mean-payoff and energy games. In Proc. FSTTCS 2010. Leibniz Int. Proc. Inf., Vol. 8. LZI, 505–516. DOI:10.4230/LIPIcs.FSTTCS.2010.505
[8] Jean-Baptiste Courtois and Sylvain Schmitz. 2014. Alternating vector addition systems with states. In Proc. MFCS 2014. Lect. Notes in Comput. Sci., Vol. 8634. Springer, 220–231. DOI:10.1007/978-3-662-44522-8_19 · Zbl 1425.68290
[9] Philippe de Groote, Bruno Guillaume, and Sylvain Salvati. 2004. Vector addition tree automata. In Proc. LICS 2004. IEEE Computer Society, 64–73. DOI:10.1109/LICS.2004.51
[10] Stéphane Demri, Marcin Jurdziński, Oded Lachish, and Ranko Lazić. 2013. The covering and boundedness problems for branching vector addition systems. J. Comput. Syst. Sci. 79, 1 (2013), 23–38. DOI:10.1016/j.jcss.2012.04.002 · Zbl 1260.68264 · doi:10.1016/j.jcss.2012.04.002
[11] Jérémie Dimino, Florent Jacquemard, and Luc Segoufin. 2013. FO2(<, + 1, ∼) on data trees, data tree automata and an extension of BVASS. (2013). http://hal.inria.fr/hal-00769249 Manuscript.
[12] Diego Figueira, Santiago Figueira, Sylvain Schmitz, and Philippe Schnoebelen. 2011. Ackermannian and primitive-recursive bounds with Dickson’s Lemma. In Proc. LICS 2011. IEEE Computer Society, 269–278. DOI:10.1109/LICS.2011.39 · doi:10.1109/LICS.2011.39
[13] Max I. Kanovich. 1995. Petri nets, Horn programs, linear logic and vector games. Ann. Pure App. Logic 75, 1–2 (1995), 107–135. DOI:10.1016/0168-0072(94)00060-G · Zbl 0829.03007 · doi:10.1016/0168-0072(94)00060-G
[14] Alexei P. Kopylov. 2001. Decidability of linear affine logic. Inform. and Comput. 164, 1 (2001), 173–198. DOI:10.1006/inco.1999.2834 · Zbl 1007.03053 · doi:10.1006/inco.1999.2834
[15] Yves Lafont. 1997. The finite model property for various fragments of linear logic. J. Symb. Log. 62, 4 (1997), 1202–1208. DOI:10.2307/2275637 · Zbl 0897.03010 · doi:10.2307/2275637
[16] Dominique Larchey-Wendling and Didier Galmiche. 2013. Nondeterministic phase semantics and the undecidability of Boolean BI. ACM Trans. Comput. Logic 14, 1 (2013), 6:1–6:41. DOI:10.1145/2422085.2422091 · Zbl 1343.03022 · doi:10.1145/2422085.2422091
[17] Ranko Lazić. 2010. The reachability problem for branching vector addition systems requires doubly-exponential space. Inf. Process. Lett. 110, 17 (2010), 740–745. DOI:10.1016/j.ipl.2010.06.008 · Zbl 1234.68139 · doi:10.1016/j.ipl.2010.06.008
[18] Patrick Lincoln, John Mitchell, Andre Scedrov, and Natarajan Shankar. 1992. Decision problems for propositional linear logic. Ann. Pure App. Logic 56, 1–3 (1992), 239–311. DOI:10.1016/0168-0072(92)90075-B · Zbl 0768.03003 · doi:10.1016/0168-0072(92)90075-B
[19] Richard Lipton. 1976. The reachability problem requires exponential space. Technical Report 62. Yale University.
[20] Martin H. Löb and Stanley S. Wainer. 1970. Hierarchies of number theoretic functions, I. Arch. Math. Logic 13 (1970), 39–51. DOI:10.1007/BF01967649 · Zbl 0211.31205 · doi:10.1007/BF01967649
[21] Ernst W. Mayr and Albert R. Meyer. 1981. The complexity of the finite containment problem for Petri Nets. J. ACM 28, 3 (1981), 561–576. DOI:10.1145/322261.322271 · Zbl 0462.68020 · doi:10.1145/322261.322271
[22] Mitsuhiro Okada and Kazushige Terui. 1999. The finite model property for various fragments of intuitionistic linear logic. J. Symb. Log. 64, 2 (1999), 790–802. DOI:10.2307/2586501 · Zbl 0930.03021 · doi:10.2307/2586501
[23] Charles Rackoff. 1978. The covering and boundedness problems for vector addition systems. Theor. Comput. Sci. 6, 2 (1978), 223–231. DOI:10.1016/0304-3975(78)90036-1 · Zbl 0368.68054 · doi:10.1016/0304-3975(78)90036-1
[24] Owen Rambow. 1994. Multiset-valued linear index grammars: imposing dominance constraints on derivations. In Proc. ACL’94. ACL Press, 263–270. DOI:10.3115/981732.981768 · doi:10.3115/981732.981768
[25] Sylvain Schmitz. 2010. On the computational complexity of dominance links in grammatical formalisms. In Proc. ACL 2010. ACL Press, 514–524.
[26] Sylvain Schmitz. 2013. Complexity Hierarchies Beyond Elementary. Preprint. Retrieved from http://arxiv.org/abs/1312.5686. · Zbl 1347.68162
[27] Sylvain Schmitz. 2014. Implicational relevance logic is 2-ExpTime-complete. In Proc. RTA-TLCA 2014. Lect. Notes in Comput. Sci., Vol. 8560. Springer, 395–409. DOI:10.1007/978-3-319-08918-8_27 · Zbl 1291.68017 · doi:10.1007/978-3-319-08918-8
[28] Philippe Schnoebelen. 2010. Revisiting Ackermann-hardness for lossy counter machines and reset Petri Nets. In Proc. MFCS 2010. Lect. Notes in Comput. Sci., Vol. 6281. Springer, 616–628. DOI:10.1007/978-3-642-15155-2_54 · Zbl 1287.68059
[29] Anne Sjerp Troelstra. 1992. Lectures on Linear Logic. CSLI Lecture Notes, Vol. 29. Center for the Study of Language and Information.
[30] Alasdair Urquhart. 1999. The complexity of decision procedures in relevance logic II. J. Symb. Log. 64, 4 (1999), 1774–1802. DOI:10.2307/2586811 · Zbl 0945.03029 · doi:10.2307/2586811
[31] Alasdair Urquhart. 2000. The complexity of linear logic with weakening. In Proc. Logic Colloquium’98. Lect. Notes in Logic, Vol. 13. ASL, 500–515. · Zbl 0949.03058
[32] Kumar Neeraj Verma and Jean Goubault-Larrecq. 2005. Karp-Miller trees for a branching extension of VASS. Disc. Math. Theor. Comput. Sci. 7, 1 (2005), 217–230. · Zbl 1152.68462
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.