Complexity hierarchies beyond elementary

DOI10.1145/2858784zbMATH Open1347.68162arXiv1312.5686OpenAlexW3125224867WikidataQ130988297 ScholiaQ130988297MaRDI QIDQ2828216FDOQ2828216

Authors: Sylvain Schmitz 

Publication date: 24 October 2016

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

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.

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

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
• Publication:3028999

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)

Cites Work

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

Cited In (39)

• Equivalence of pushdown automata via first-order grammars
• On a Temporal Logic of Prefixes and Infixes.
• Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence
• Reachability analysis of low-order discrete state reaction networks obeying conservation laws
• Augmenting ATL with strategy contexts
• 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
• Title not available (Why is that?)
• Separation logics and modalities: a survey
• On functions weakly computable by pushdown Petri nets and related systems
• Polynomial time coverability analysis in discrete state chemical reaction network subclasses
• An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning
• Verification of flat FIFO systems
• Polynomial time reachability analysis in discrete state chemical reaction networks obeying conservation laws
• Coverability trees for Petri nets with unordered data
• The fluted fragment with transitive relations
• Forward analysis and model checking for trace bounded WSTS
• Canonical models and the complexity of modal team logic
• Title not available (Why is that?)
• Zeno, Hercules, and the Hydra: safety metric temporal logic is Ackermann-complete
• Modal logics and local quantifiers: a zoo in the elementary hierarchy
• Title not available (Why is that?)
• 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
• When symmetries are not enough: a hierarchy of hard constraint satisfaction problems
• The fluted fragment revisited
• An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning
• Title not available (Why is that?)
• The fixed initial credit problem for partial-observation energy games is \textsc{Ack}-complete
• Lower bounds for the reachability problem in fixed dimensional VASSes
• On the termination and structural termination problems for counter machines with incrementing errors
• On Composing Finite Forests with Modal Logics
• The Fluted Fragment with Transitivity
• 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

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)