×

zbMATH — the first resource for mathematics

Complexity hierarchies beyond elementary. (English) Zbl 1347.68162

MSC:
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15 Complexity of computation (including implicit computational complexity)
03D20 Recursive functions and relations, subrecursive hierarchies
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Parosh A. Abdulla, Karlis Čerāns, Bengt Jonsson, and Yih-Kuen Tsay. 2000. Algorithmic analysis of programs with well quasi-ordered domains. Information and Computation 160, 1–2, 109–127. DOI:http://dx.doi.org/10.1006/inco.1999.2843 · Zbl 1046.68567 · doi:10.1006/inco.1999.2843
[2] Parosh A. Abdulla and Giorgio Delzanno. 2006. On the coverability problem for constrained multiset rewriting. In Proceedings of the 2006 AVIS Conference.
[3] Parosh A. Abdulla, Giorgio Delzanno, and Laurent Van Begin. 2011. A classification of the expressive power of well-structured transition systems. Information and Computation 209, 3, 248–279. DOI:http://dx.doi.org/10.1016/j.ic.2010.11.003 · Zbl 1217.68146 · doi:10.1016/j.ic.2010.11.003
[4] Parosh A. Abdulla and Bengt Jonsson. 1996. Verifying programs with unreliable channels. Information and Computation 127, 2, 91–101. DOI:http://dx.doi.org/10.1006/inco.1996.0053 · Zbl 0856.68096 · doi:10.1006/inco.1996.0053
[5] Parosh A. Abdulla and Aletta Nylén. 2001. Timed Petri nets and BQOs. In Applications and Theory of Petri Nets 2001. Lecture Notes in Computer Science, Vol. 2075. Springer, 53–70. DOI:http://dx.doi.org/10.1007/3-540-45740-2_5 · Zbl 0986.68092 · doi:10.1007/3-540-45740-2_5
[6] Sergio Abriola, Santiago Figueira, and Gabriel Senno. 2015. Linearizing well-quasi orders and bounding the length of bad sequences. Theoretical Computer Science 603, 3–22. DOI:http://dx.doi.org/10.1016/j.tcs.2015.07.012 · Zbl 1347.03086 · doi:10.1016/j.tcs.2015.07.012
[7] Rajeev Alur and David L. Dill. 1994. A theory of timed automata. Theoretical Computer Science 126, 2, 183–235. DOI:http://dx.doi.org/10.1016/0304-3975(94)90010-8 · Zbl 0803.68071 · doi:10.1016/0304-3975(94)90010-8
[8] Mohamed Faouzi Atig, Ahmed Bouajjani, Sebastian Burckhardt, and Madanlal Musuvathi. 2010. On the verification problem for weak memory models. In Proceedings of the 2010 POPL Conference. ACM, New York, NY, 7–18. DOI:http://dx.doi.org/10.1145/1706299.1706303 · Zbl 1312.68050 · doi:10.1145/1706299.1706303
[9] Pablo Barceló, Diego Figueira, and Leonid Libkin. 2013. Graph logics with rational relations. Logical Methods in Computer Science 9, 3, Article No. 1. DOI:http://dx.doi.org/10.2168/LMCS-9(3:1)2013 · Zbl 1272.03147 · doi:10.2168/LMCS-9(3:1)2013
[10] Arnold Beckmann. 2001. Exact bounds for lengths of reductions in typed λ-calculus. Journal of Symbolic Logic 66, 3, 1277–1285. DOI:http://dx.doi.org/10.2307/2695106 · Zbl 1159.03305 · doi:10.2307/2695106
[11] Michel Blockelet and Sylvain Schmitz. 2011. Model-checking coverability graphs of vector addition systems. In Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, 6907. Springer, 108–119. DOI:http://dx.doi.org/10.1007/978-3-642-22993-0_13 · Zbl 1343.68152 · doi:10.1007/978-3-642-22993-0_13
[12] Rémi Bonnet, Alain Finkel, Serge Haddad, and Fernando Rosa-Velardo. 2010. Comparing Petri Data Nets and Timed Petri Nets. Research Report LSV-10-23. LSV, ENS Cachan. http://lsv.fr/Publis/rrpublis?onlykey=rr-lsv-10-23
[13] Patricia Bouyer, Nicolas Markey, Joël O. Ouaknine, Philippe Schnoebelen, and James B. Worrell. 2012. On termination and invariance for faulty channel machines. Formal Aspects of Computing 24, 4–6, 595–607. DOI:http://dx.doi.org/10.1007/s00165-012-0234-7 · Zbl 1259.68142 · doi:10.1007/s00165-012-0234-7
[14] Davide Bresolin, Dario Della Monica, Angelo Montanari, Pietro Sala, and Guido Sciavicco. 2012. Interval temporal logics over finite linear orders: The complete picture. In Proceedings of the 2012 ECAI Conference. 199–204. DOI:http://dx.doi.org/10.3233/978-1-61499-098-7-199 · Zbl 1327.03012
[15] Gérard Cécé, Alain Finkel, and S. Purushothaman Iyer. 1996. Unreliable channels are easier to verify than perfect channels. Information and Computation 124, 1, 20–31. DOI:http://dx.doi.org/10.1006/inco.1996.0003 · Zbl 0844.68035 · doi:10.1006/inco.1996.0003
[16] Pierre Chambart and Philippe Schnoebelen. 2007. Post embedding problem is not primitive recursive, with applications to channel systems. In FSTTCS 2007: Foundations of Software Technology and Theoretic Computer Science. Lecture Notes in Computer Science, Vol. 4855. Springer, 265–276. DOI:http://dx.doi.org/10.1007/978-3-540-77050-3_22 · Zbl 1136.03030 · doi:10.1007/978-3-540-77050-3_22
[17] Pierre Chambart and Philippe Schnoebelen. 2008a. The ω-regular post embedding problem. In Foundations of Software Science and Computational Structures. Lecture Notes in Computer Science, Vol. 4962. Springer, 97–111. DOI:http://dx.doi.org/10.1007/978-3-540-78499-9_8 · Zbl 1139.03031 · doi:10.1007/978-3-540-78499-9_8
[18] Pierre Chambart and Philippe Schnoebelen. 2008b. The ordinal recursive complexity of lossy channel systems. In Proceedings of the 2008 LICS Conference. IEEE, Los Alamitos, CA, 205–216. DOI:http://dx.doi.org/10.1109/LICS.2008.47 · doi:10.1109/LICS.2008.47
[19] E. Adam Cichoń and Elias Tahhan Bittar. 1998. Ordinal recursive bounds for Higman’s theorem. Theoretical Computer Science 201, 1–2, 63–84. DOI:http://dx.doi.org/10.1016/S0304-3975(97)00009-1 · Zbl 0902.68100 · doi:10.1016/S0304-3975(97)00009-1
[20] Peter Clote. 1986. On the finite containment problem for Petri nets. Theoretical Computer Science 43, 99–105. DOI:http://dx.doi.org/10.1016/0304-3975(86)90169-6 · Zbl 0614.68047 · doi:10.1016/0304-3975(86)90169-6
[21] Peter Clote. 1999. Computation models and function algebras. In Handbook of Computability Theory, E. R. Griffor (Ed.). Studies in Logic and the Foundations of Mathematics, Vol. 140. Elsevier, 589–681. DOI:http://dx.doi.org/10.1016/S0049-237X(99)80033-0 · Zbl 0942.68049 · doi:10.1016/S0049-237X(99)80033-0
[22] M. Dauchet and S. Tison. 1990. The theory of ground rewrite systems is decidable. In Proceedings of the 1990 LICS Conference. IEEE, Los Alamitos, CA, 242–248. DOI:http://dx.doi.org/10.1109/LICS.1990.113750 · doi:10.1109/LICS.1990.113750
[23] Dick H. J. de Jongh and Rohit Parikh. 1977. Well-partial orderings and hierarchies. Indagationes Mathematicae 39, 3, 195–207. http://dx:doi:org/10:1016/1385-7258(77)90067-1 · Zbl 0435.06004
[24] Normann Decker and Daniel Thoma. 2015. On Freeze LTL with ordered attributes. Preprint. Available at http://arxiv.org/abs/1504.06355 · Zbl 06591825
[25] Stéphane Demri and Ranko Lazić. 2009. LTL with the freeze quantifier and register automata. ACM Transactions on Computational Logic 10, 3, Article No. 16. DOI:http://dx.doi.org/10.1145/1507244.1507246 · Zbl 1351.68158 · doi:10.1145/1507244.1507246
[26] J. Michael Dunn and Greg Restall. 2002. Relevance logic. In Handbook of Philosophical Logic, D. M. Gabbay and F. Guenthner (Eds.), Vol. 6. Kluwer, 1–128. DOI:http://dx.doi.org/10.1007/978-94-017-0460-1_1 · doi:10.1007/978-94-017-0460-1_1
[27] Jacob Elgaard, Nils Klarlund, and Anders Møller. 1998. MONA 1.x: New techniques for WS1S and WS2S. In Computer Aided Verification. Lecture Notes in Computer Science, Vol. 1427. Springer, 516–520. DOI:http://dx.doi.org/10.1007/BFb0028773 · doi:10.1007/BFb0028773
[28] Patrick C. Fischer, Albert R. Meyer, and Arnold L. Rosenberg. 1968. Counter machines and counter languages. Mathematical Systems Theory 2, 3, 265–283. DOI:http://dx:doi:org/10:1007/BF01694011 · Zbl 0165.32002
[29] Matthew V. H. Fairtlough and Stanley S. Wainer. 1992. Ordinal complexity of recursive definitions. Information and Computation 99, 2, 123–153. DOI:http://dx.doi.org/10.1016/0890-5401(92)90027-D · Zbl 0768.03027 · doi:10.1016/0890-5401(92)90027-D
[30] Matthew V. H. Fairtlough and Stanley S. Wainer. 1998. Hierarchies of provably recursive functions. In Handbook of Proof Theory, S. Buss (Ed.). Studies in Logic and the Foundations of Mathematics, Vol. 137. Elsevier, 149–207. DOI:http://dx.doi.org/10.1016/S0049-237X(98)80018-9 · Zbl 0961.03053 · doi:10.1016/S0049-237X(98)80018-9
[31] Solomon Feferman. 1962. Classification of recursive functions by means of hierarchies. Transactions of the American Mathematical Society 104, 101–122. DOI:http://dx.doi.org/10.1090/S0002-9947-1962-0142453-3 · Zbl 0106.00602 · doi:10.1090/S0002-9947-1962-0142453-3
[32] Diego Figueira. 2012. Alternating register automata on finite words and trees. Logical Methods in Computer Science 8, 1, Article No. 22. DOI:http://dx.doi.org/10.2168/LMCS-8(1:22)2012 · Zbl 1238.68074 · doi:10.2168/LMCS-8(1:22)2012
[33] Diego Figueira, Santiago Figueira, Sylvain Schmitz, and Philippe Schnoebelen. 2011. Ackermannian and primitive-recursive bounds with Dickson’s lemma. In Proceedings of the 2011 LICS Conference. IEEE, Los Alamitos, CA, 269–278. DOI:http://dx.doi.org/10.1109/LICS.2011.39 · doi:10.1109/LICS.2011.39
[34] Diego Figueira, Piotr Hofman, and Sławomir Lasota. 2015. Relating timed and register automata. Mathematical Structures in Computer Science. To appear. DOI:http://dx.doi.org/10.1017/S0960129514000322 · Zbl 1362.68138 · doi:10.1017/S0960129514000322
[35] Diego Figueira and Luc Segoufin. 2009. Future-looking logics on data words and trees. In Mathematical Foundations of Computer Science 2009. Lecture Notes in Computer Science, Vol. 5734. Springer, 331–343. DOI:http://dx:doi:org/10:1007/978-3-642-03816-729 · Zbl 1250.03050
[36] Alain Finkel. 1987. A generalization of the procedure of Karp and Miller to well structured transition systems. In Automata, Languages and Programming. Lecture Notes in Computer Science, Vol. 267. Springer, 499–508. DOI:http://dx.doi.org/10.1007/3-540-18088-5_43 · Zbl 0633.68052 · doi:10.1007/3-540-18088-5_43
[37] Alain Finkel and Philippe Schnoebelen. 2001. Well-structured transition systems everywhere! Theoretical Computer Science 256, 1–2, 63–92. DOI:http://dx.doi.org/10.1016/S0304-3975(00)00102-X · Zbl 0973.68170 · doi:10.1016/S0304-3975(00)00102-X
[38] Harvey M. Friedman. 1999. Some decision problems of enormous complexity. In Proceedings of the 1999 LICS Conference. IEEE, Los Alamitos, CA, 2–13. DOI:http://dx.doi.org/10.1109/LICS.1999.782577 · doi:10.1109/LICS.1999.782577
[39] Andrzej Grzegorczyk. 1953. Some classes of recursive functions. Rozprawy Matematyczne 4, 1–46. http://matwbn.icm.edu.pl/ksiazki/rm/rm04/rm0401.pdf. · Zbl 0052.24902
[40] Christoph Haase, Sylvain Schmitz, and Philippe Schnoebelen. 2014. The power of priority channel systems. Logical Methods in Computer Science 10, 4, Article No. 4. DOI:http://dx.doi.org/10.2168/LMCS-10(4:4)2014 · Zbl 1448.68341 · doi:10.2168/LMCS-10(4:4)2014
[41] Michel Hack. 1976. The equality problem for vector addition systems is undecidable. Theoretical Computer Science 2, 1, 77–95. DOI:http://dx.doi.org/10.1016/0304-3975(76)90008-6 · Zbl 0357.68038 · doi:10.1016/0304-3975(76)90008-6
[42] Serge Haddad, Sylvain Schmitz, and Philippe Schnoebelen. 2012. The ordinal-recursive complexity of timed-arc Petri nets, data nets, and other enriched nets. In Proceedings of the 2012 LICS Conference. IEEE, Los Alamitos, CA, 355–364. DOI:http://dx.doi.org/10.1109/LICS.2012.46 · Zbl 1362.68214 · doi:10.1109/LICS.2012.46
[43] Matthew Hague. 2014. Senescent ground tree rewriting systems. In Proceedings of the 2014 CSL-LICS Conference. ACM, New York, NY, Article No. 48. DOI:http://dx.doi.org/10.1145/2603088.2603112 · Zbl 1401.68135 · doi:10.1145/2603088.2603112
[44] Joseph Y. Halpern and Yoav Shoham. 1991. A propositional modal logic of time intervals. Journal of the ACM 38, 4, 935–962. DOI:http://dx.doi.org/10.1145/115234.115351 · Zbl 0799.68175 · doi:10.1145/115234.115351
[45] Piotr Hofman and Patrick Totzke. 2014. Trace inclusion for one-counter nets revisited. In Reachability Problems. Lecture Notes in Computer Science, Vol. 8762. Springer, 151–162. DOI:http://dx.doi.org/10.1007/978-3-319-11439-2_12 · Zbl 1393.68117 · doi:10.1007/978-3-319-11439-2_12
[46] Petr Jančar. 1995. Undecidability of bisimilarity for Petri nets and some related problems. Theoretical Computer Science 148, 2, 281–301. DOI:http://dx.doi.org/10.1016/0304-3975(95)00037-W · Zbl 0873.68147 · doi:10.1016/0304-3975(95)00037-W
[47] Petr Jančar. 2001. Nonprimitive recursive complexity and undecidability for Petri net equivalences. Theoretical Computer Science 256, 1–2, 23–30. DOI:http://dx.doi.org/10.1016/S0304-3975(00)00100-6 · Zbl 0974.68130 · doi:10.1016/S0304-3975(00)00100-6
[48] Marcin Jurdziński and Ranko Lazić. 2011. Alternating automata on data trees and XPath satisfiability. ACM Transactions on Computational Logic 12, 3, Article No. 19. DOI:http://dx:doi:org/10:1145/1929954:1929956 · Zbl 1351.68141
[49] Prateek Karandikar and Sylvain Schmitz. 2013. The parametric ordinal-recursive complexity of Post embedding problems. In Foundations of Software Science and Computation Structures. Lecture Notes in Computer Science, Vol. 7794. Springer, 273–288. DOI:http://dx.doi.org/10.1007/978-3-642-37075-5_18 · Zbl 1260.68179 · doi:10.1007/978-3-642-37075-5_18
[50] Prateek Karandikar and Philippe Schnoebelen. 2012. Cutting through regular post embedding problems. In Computer Science—Theory and Applications. Lecture Notes in Computer Science, Vol. 7353. Springer, 229–240. DOI:http://dx.doi.org/10.1007/978-3-642-30642-6_22 · Zbl 1315.03064 · doi:10.1007/978-3-642-30642-6_22
[51] S. Rao Kosaraju. 1982. Decidability of reachability in vector addition systems. In Proceedings of the 1982 STOC Conference. ACM, New York, NY, 267–281. DOI:http://dx.doi.org/10.1145/800070.802201 · doi:10.1145/800070.802201
[52] Ron Koymans. 1990. Specifying real-time properties with metric temporal logic. Real-Time Systems 2, 4, 255–299. DOI:http://dx.doi.org/10.1007/BF01995674 · doi:10.1007/BF01995674
[53] Joseph B. Kruskal. 1972. The theory of well-quasi-ordering: A frequently discovered concept. Journal of Combinatorial Theory, Series A 13, 3, 297–305. DOI:http://dx.doi.org/10:1016/0097-3165(72)90063-5 · Zbl 0244.06002
[54] Jean-Luc Lambert. 1992. A structure to decide reachability in Petri nets. Theoretical Computer Science 99, 1, 79–104. DOI:http://dx.doi.org/10.1016/0304-3975(92)90173-D · Zbl 0769.68104 · doi:10.1016/0304-3975(92)90173-D
[55] Sławomir Lasota and Igor Walukiewicz. 2008. Alternating timed automata. ACM Transactions on Computational Logic 9, 2, Article No. 10. DOI:http://dx.doi.org/10.1145/1342991.1342994 · Zbl 1367.68172 · doi:10.1145/1342991.1342994
[56] Ranko Lazić, Tom Newcomb, Joël O. Ouaknine, Andrew W. Roscoe, and James B. Worrell. 2008. Nets with tokens which carry data. Fundamenta Informaticae 88, 3, 251–274. · Zbl 1154.68090
[57] Ranko Lazić, Joël O. Ouaknine, and James B. Worrell. 2013. Zeno, Hercules and the Hydra: Downward rational termination is Ackermannian. In Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, Vol. 8087. Springer, 643–654. DOI:http://dx.doi.org/10.1007/978-3-642-40313-2_57 · Zbl 1400.03034 · doi:10.1007/978-3-642-40313-2_57
[58] Ranko Lazić and Sylvain Schmitz. 2015. Non-elementary complexities for branching VASS, MELL, and extensions. ACM Transactions on Computational Logic 16, 3, Article No. 20. DOI:http://dx.doi.org/10.1145/2733375 · Zbl 1354.68128 · doi:10.1145/2733375
[59] Jérôme Leroux. 2011. Vector addition system reachability problem: A short self-contained proof. In Proceedings of the 2011 POPL Conference. ACM, New York, NY, 307–316. DOI:http://dx.doi.org/10.1145/1926385.1926421 · Zbl 1284.68429 · doi:10.1145/1926385.1926421
[60] Jérôme Leroux and Sylvain Schmitz. 2015. Demystifying reachability in vector addition systems. In Proceedings of the 2015 LICS Conference. IEEE, Los Alamitos, CA, 56–67. DOI:http://dx.doi.org/10.1109/LICS.2015.16 · Zbl 1392.68308 · doi:10.1109/LICS.2015.16
[61] Richard J. Lipton. 1976. The Reachability Problem Requires Exponential Space. Technical Report 62. Department of Computer Science, Yale University, New Haven, CT. http://www.cs.yale.edu/publications/techreports/tr63.pdf.
[62] Martin H. Löb and Stanley S. Wainer. 1970. Hierarchies of number theoretic functions, I. Archive for Mathematical Logic 13, 39–51. DOI:http://dx.doi.org/10.1007/BF01967649 · Zbl 0211.31205 · doi:10.1007/BF01967649
[63] Ernst W. Mayr. 1981. An algorithm for the general Petri net reachability problem. In Proceedings of the 1981 STOC Conference. ACM, Los Alamitos, CA, 238–246. DOI:http://dx.doi.org/10.1145/800076.802477 · doi:10.1145/800076.802477
[64] Ernst W. Mayr and Albert R. Meyer. 1981. The complexity of the finite containment problem for Petri nets. Journal of the ACM 28, 3, 561–576. DOI:http://dx.doi.org/10.1145/322261.322271 · Zbl 0462.68020 · doi:10.1145/322261.322271
[65] Kenneth McAloon. 1984. Petri nets and large finite sets. Theoretical Computer Science 32, 1–2, 173–183. DOI:http://dx.doi.org/10.1016/0304-3975(84)90029-X · Zbl 0569.68046 · doi:10.1016/0304-3975(84)90029-X
[66] Albert R. Meyer. 1975a. The inherent computational complexity of theories of ordered sets. In Proceedings of the International Congress of Mathematicians. 477–482. http://www.mathunion.org/ICM/ICM1974.2/Main/icm1974.2.0477.0482.ocr.pdf. · Zbl 0361.02061
[67] Albert R. Meyer. 1975b. Weak monadic second order theory of successor is not elementary-recursive. In Logic Colloquium. Lecture Notes in Mathematics, Vol. 453. Springer, 132–154. DOI:http://dx.doi.org/10.1007/BFb0064872 · doi:10.1007/BFb0064872
[68] Albert R. Meyer and Dennis M. Ritchie. 1967. The complexity of loop programs. In Proceedings of the 1967 ACM Conference. ACM, New York, NY, 465–469. DOI:http://dx.doi.org/10.1145/800196.806014 · doi:10.1145/800196.806014
[69] Angelo Montanari, Gabriele Puppis, and Pietro Sala. 2010. Maximal decidable fragments of Halpern and Shoham’s modal logic of intervals. In Automata, Languages and Programming. Lecture Notes in Computer Science, Vol. 6199. Springer, 345–356. DOI:http://dx.doi.org/10.1007/978-3-642-14162-1_29 · Zbl 1288.03017 · doi:10.1007/978-3-642-14162-1_29
[70] Piergiorgio Odifreddi. 1999. Classical Recursion Theory, Vol. II. Studies in Logic and the Foundations of Mathematics, Vol. 143. Elsevier. DOI:http://dx:doi:org/10:1016/S0049-237X(99)80040-8
[71] Eran Omri and Andreas Weiermann. 2009. Classifying the phase transition threshold for Ackermannian functions. Annals of Pure and Applied Logic 158, 3, 156–162. DOI:http://dx:doi:org/10:1016/j:apal:2007:02:004
[72] Joël O. Ouaknine and James B. Worrell. 2006. On metric temporal logic and faulty Turing machines. In Foundations of Software Science and Computation Structures. Lecture Notes in Computer Science, Vol. 3921. Springer, 217–230. DOI:http://dx.doi.org/10.1007/11690634_15 · Zbl 1180.03021 · doi:10.1007/11690634_15
[73] Joël O. Ouaknine and James B. Worrell. 2007. On the decidability and complexity of metric temporal logic over finite words. Logical Methods in Computer Science 3, 1, Article No. 8. DOI:http://dx.doi.org/10.2168/LMCS-3(1:8)2007 · Zbl 1128.03008 · doi:10.2168/LMCS-3(1:8)2007
[74] Charles Rackoff. 1978. The covering and boundedness problems for vector addition systems. Theoretical Computer Science 6, 2, 223–231. DOI:http://dx.doi.org/10.1016/0304-3975(78)90036-1 · Zbl 0368.68054 · doi:10.1016/0304-3975(78)90036-1
[75] Robert W. Ritchie. 1963. Classes of predictably computable functions. Transactions of the American Mathematical Society 106, 1, 139–173. DOI:http://dx.doi.org/10.1090/S0002-9947-1963-0158822-2 · Zbl 0107.01001 · doi:10.1090/S0002-9947-1963-0158822-2
[76] Robert W. Ritchie. 1965. Classes of recursive functions based on Ackermann’s function. Pacific Journal of Mathematics 15, 3, 1027–1044. DOI:http://dx.doi.org/10.2140/pjm.1965.15.1027 · Zbl 0133.24903 · doi:10.2140/pjm.1965.15.1027
[77] Fernando Rosa-Velardo. 2014. Ordinal Recursive Complexity of Unordered Data Nets. Technical Report TR-4-14. Departamento de Sistemas Informáticos y Computación, Universidad Complutense de Madrid. https://federwin.sip.ucm.es/sic/investigacion/publicaciones/pdfs/TR-04-14.pdf.
[78] Harvey E. Rose. 1984. Subrecursion: Functions and Hierarchies. Oxford Logic Guides, Vol. 9. Clarendon Press. · Zbl 0539.03018
[79] Sylvain Schmitz and Philippe Schnoebelen. 2011. Multiply-recursive upper bounds with Higman’s lemma. In Automata, Languages and Programming. Lecture Notes in Computer Science, Vol. 6756. Springer, 441–452. DOI:http://dx.doi.org/10.1007/978-3-642-22012-8_35 · Zbl 1333.68179 · doi:10.1007/978-3-642-22012-8_35
[80] Sylvain Schmitz and Philippe Schnoebelen. 2012. Algorithmic Aspects of WQO Theory. Retrieved December 9, 2016, from http://cel.archives-ouvertes.fr/cel-00727025. · Zbl 1362.68214
[81] Sylvain Schmitz and Philippe Schnoebelen. 2013. The power of well-structured systems. In CONCUR 2013—Concurrency Theory. Lecture Notes in Computer Science, Vol. 8052. Springer, 5–24. DOI:http://dx.doi.org/10.1007/978-3-642-40184-8_2 · Zbl 1390.68488 · doi:10.1007/978-3-642-40184-8_2
[82] Philippe Schnoebelen. 2002. Verifying lossy channel systems has nonprimitive recursive complexity. Information Processing Letters 83, 5, 251–261. DOI:http://dx.doi.org/10.1016/S0020-0190(01)00337-4 · Zbl 1043.68016 · doi:10.1016/S0020-0190(01)00337-4
[83] Philippe Schnoebelen. 2010. Revisiting Ackermann-hardness for lossy counter machines and reset Petri nets. In Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, Vol. 6281. Springer, 616–628. DOI:http://dx.doi.org/10.1007/978-3-642-15155-2_54 · Zbl 1287.68059 · doi:10.1007/978-3-642-15155-2_54
[84] Helmut Schwichtenberg. 1982. Complexity of normalization in the pure typed lambda-calculus. Studies in Logic and the Foundations of Mathematics 110, 453–457. DOI:http://dx.doi.org/10.1016/S0049-237X(09)70143-0 · Zbl 0537.03028 · doi:10.1016/S0049-237X(09)70143-0
[85] Helmut Schwichtenberg and Stanley S. Wainer. 2012. Proofs and Computation. Cambridge University Press. · Zbl 1294.03006
[86] Richard Statman. 1979. The typed λ-calculus is not elementary recursive. Theoretical Computer Science 9, 1, 73–81. DOI:http://dx.doi.org/10.1016/0304-3975(79)90007-0 · Zbl 0411.03050 · doi:10.1016/0304-3975(79)90007-0
[87] Larry J. Stockmeyer and Albert R. Meyer. 1973. Word problems requiring exponential time. In Proceedings of the 1973 STOC Conference. ACM, New York, NY, 1–9. DOI:http://dx.doi.org/10.1145/800125.804029 · Zbl 0359.68050 · doi:10.1145/800125.804029
[88] Tony Tan. 2010. On pebble automata for data languages with decidable emptiness problem. Journal of Computer and System Sciences 76, 8, 778–791. DOI:http://dx:doi:org/10:1016/j:jcss:2010:03:004 · Zbl 1208.68142
[89] Nikos Tzevelekos and Radu Grigore. 2013. History-register automata. In Foundations of Software Science and Computation Structures. Lecture Notes in Computer Science, Vol. 7794. Springer, 273–288. DOI:http://dx:doi:org/10:1007/978-3-642-37075-52 · Zbl 1260.68118
[90] Alasdair Urquhart. 1984. The undecidability of entailment and relevant implication. Journal of Symbolic Logic 49, 4, 1059–1073. DOI:http://dx.doi.org/10.2307/2274261 · Zbl 0581.03011 · doi:10.2307/2274261
[91] Alasdair Urquhart. 1999. The complexity of decision procedures in relevance logic II. Journal of Symbolic Logic 64, 4, 1774–1802. DOI:http://dx.doi.org/10.2307/2586811 · Zbl 0945.03029 · doi:10.2307/2586811
[92] Sergei Vorobyov. 2004. The most nonelementary theory. Information and Computation 190, 2, 196–219. DOI:http://dx:doi:org/10:1016/j:ic:2004:02:002 · Zbl 1064.03029
[93] Stanley S. Wainer. 1970. A classification of the ordinal recursive functions. Archive for Mathematical Logic 13, 3, 136–153. DOI:http://dx.doi.org/10.1007/BF01973619 · Zbl 0228.02027 · doi:10.1007/BF01973619
[94] Andreas Weiermann. 1994. Complexity bounds for some finite forms of Kruskal’s theorem. Journal of Symbolic Computation 18, 5, 463–488. DOI:http://dx.doi.org/10.1006/jsco.1994.1059 · Zbl 0827.68055 · doi:10.1006/jsco.1994.1059
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.