Complexity hierarchies beyond elementary

DOI10.1145/2858784MaRDI QIDQ2828216zbMATH OpenOpenAlexWikidataFDO

Authors Sylvain Schmitz

Publication date 24 October 2016

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.5686

zbMATH Keywords

well-quasi-ordersubrecursionfast-growing complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20)

Abstract: We introduce a hierarchy of fast-growing complexity classes and show its suitability for completeness statements of many non elementary problems. This hierarchy allows the classification of many decision problems with a non-elementary complexity, which occur naturally in logic, combinatorics, formal languages, verification, etc., with complexities ranging from simple towers of exponentials to Ackermannian and beyond.

Recommendations

• Logical Approaches to Computational Barriers
• scientific article; zbMATH DE number 3841818
• scientific article; zbMATH DE number 17786
• Delineating classes of computational complexity via second order theories with weak set existence principles. I
• scientific article; zbMATH DE number 4016888

Cites work

• scientific article; zbMATH DE number 3853055 (Why is no real title available?)
• scientific article; zbMATH DE number 3857078 (Why is no real title available?)
• scientific article; zbMATH DE number 4030997 (Why is no real title available?)
• scientific article; zbMATH DE number 3677903 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3561331 (Why is no real title available?)
• scientific article; zbMATH DE number 1215495 (Why is no real title available?)
• scientific article; zbMATH DE number 1755138 (Why is no real title available?)
• scientific article; zbMATH DE number 1390027 (Why is no real title available?)
• scientific article; zbMATH DE number 3083488 (Why is no real title available?)
• A classification of the expressive power of well-structured transition systems
• A classification of the ordinal recursive functions
• A propositional modal logic of time intervals
• A structure to decide reachability in Petri nets
• A theory of timed automata
• Algorithmic analysis of programs with well quasi-ordered domains.
• Alternating automata on data trees and XPath satisfiability
• Alternating register automata on finite words and trees
• Alternating timed automata
• Classes of Predictably Computable Functions
• Classes of recursive functions based on Ackermann's function
• Classifications of Recursive Functions by Means of Hierarchies
• Complexity bounds for some finite forms of Kruskal's theorem
• Counter machines and counter languages
• Demystifying Reachability in Vector Addition Systems
• Exact bounds for lengths of reductions in typed -calculus
• Foundations of Software Science and Computation Structures
• Future-Looking Logics on Data Words and Trees
• Graph logics with rational relations
• Hierarchies of number-theoretic functions. I
• History-register automata
• Interval temporal logics over finite linear orders: the complete picture
• LTL with the freeze quantifier and register automata
• Linearizing well quasi-orders and bounding the length of bad sequences
• Maximal decidable fragments of Halpern and Shoham's modal logic of intervals
• Model Checking Coverability Graphs of Vector Addition Systems
• Multiply-recursive upper bounds with Higman's lemma
• Nets with tokens which carry data
• Nonprimitive recursive complexity and undecidability for Petri net equivalences
• On freeze LTL with ordered attributes
• On pebble automata for data languages with decidable emptiness problem
• On termination and invariance for faulty channel machines
• On the decidability and complexity of Metric Temporal Logic over finite words
• On the finite containment problem for Petri nets
• On the verification problem for weak memory models
• Ordinal complexity of recursive definitions
• Ordinal recursive bounds for Higman's theorem
• Petri nets and large finite sets
• Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems
• Proofs and computations
• Relating timed and register automata
• Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets
• Senescent ground tree rewrite systems
• The Complexity of the Finite Containment Problem for Petri Nets
• The complexity of decision procedures in relevance logic II
• The covering and boundedness problems for vector addition systems
• The equality problem for vector addition systems is undecidable
• The most nonelementary theory
• The ordinal-recursive complexity of timed-arc Petri nets, data nets, and other enriched nets
• The parametric ordinal-recursive complexity of Post embedding problems
• The power of priority channel systems
• The power of well-structured systems
• The theory of well-quasi-ordering: a frequently discovered concept
• The typed lambda-calculus is not elementary recursive
• The undecidability of entailment and relevant implication
• The ω-Regular Post Embedding Problem
• Trace inclusion for one-counter nets revisited
• Undecidability of bisimilarity for Petri nets and some related problems
• Unreliable channels are easier to verify than perfect channels
• Vector addition system reachability problem, a short self-contained proof
• Verifying lossy channel systems has nonprimitive recursive complexity.
• Verifying programs with unreliable channels
• Well-structured transition systems everywhere!
• Zeno, Hercules and the Hydra: downward rational termination is Ackermannian

Cited in

(56)

• Equivalence of pushdown automata via first-order grammars
• New lower bounds for reachability in vector addition systems
• On a Temporal Logic of Prefixes and Infixes.
• Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence
• Augmenting ATL with strategy contexts
• Reachability analysis of low-order discrete state reaction networks obeying conservation laws
• The semilinear home-space problem is Ackermann-complete for Petri nets
• On the separability problem of VASS reachability languages
• Soundness of reset workflow nets
• The ideal view on Rackoff's coverability technique
• The Parametric Complexity of Lossy Counter Machines
• Adding the relation \textit{Meets} to the temporal logic of prefixes and infixes makes it EXPSPACE-complete
• scientific article; zbMATH DE number 7577569 (Why is no real title available?)
• Separation logics and modalities: a survey
• On functions weakly computable by pushdown Petri nets and related systems
• Coverability trees for Petri nets with unordered data
• Verification of flat FIFO systems
• An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning
• The fluted fragment with transitive relations
• Forward analysis and model checking for trace bounded WSTS
• Polynomial time coverability analysis in discrete state chemical reaction network subclasses
• Polynomial time reachability analysis in discrete state chemical reaction networks obeying conservation laws
• Canonical models and the complexity of modal team logic
• scientific article; zbMATH DE number 7561347 (Why is no real title available?)
• On the home-space problem for Petri nets and its Ackermannian complexity
• Zeno, Hercules, and the Hydra: safety metric temporal logic is Ackermann-complete
• Modal logics and local quantifiers: a zoo in the elementary hierarchy
• scientific article; zbMATH DE number 5175850 (Why is no real title available?)
• Universal quantification makes automatic structures hard to decide
• Challenges of the reachability problem in infinite-state systems (invited paper)
• Improved lower bounds for reachability in vector addition systems
• Fluted logic with counting
• Bisimulation equivalence of pushdown automata is Ackermann-complete
• Hrushovski's encoding and -categorical CSP monsters
• When symmetries are not enough: a hierarchy of hard constraint satisfaction problems
• Ackermannian completion of separators
• Parameterized broadcast networks with registers: from NP to the frontiers of decidability
• Simply typed convertibility is \textsc{Tower}-complete even for safe lambda-terms
• The fluted fragment revisited
• An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning
• The fixed initial credit problem for partial-observation energy games is \textsc{Ack}-complete
• scientific article; zbMATH DE number 3841818 (Why is no real title available?)
• Improved algorithm for reachability in d-VASS
• Integer linear-exponential programming in NP by quantifier elimination
• On the termination and structural termination problems for counter machines with incrementing errors
• Lower bounds for the reachability problem in fixed dimensional VASSes
• Tight length theorems for multiset extensions of Higman's lemma
• Linear recurrence sequence automata and the addition of abstract numeration systems
• Finite relational semantics for language Kleene algebra with complement
• On Composing Finite Forests with Modal Logics
• The Fluted Fragment with Transitivity
• The adjacent fragment and Quine's limits of decision
• Complexity and behind the horizon cut off
• The ideal approach to computing closed subsets in well-quasi-orderings
• Deciding fast termination for probabilistic VASS with nondeterminism
• Ordinal recursive complexity of unordered data nets

Describes a project that uses

Uses Software

• MONA

This page was built for publication: Complexity hierarchies beyond elementary

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828216)