Complexity Hierarchies beyond Elementary

DOI10.1145/2858784zbMath1347.68162arXiv1312.5686OpenAlexW3125224867MaRDI QIDQ2828216

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 of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (33)

Zeno, Hercules, and the Hydra ⋮ On Composing Finite Forests with Modal Logics ⋮ Forward analysis and model checking for trace bounded WSTS ⋮ Polynomial Time Reachability Analysis in Discrete State Chemical Reaction Networks Obeying Conservation Laws ⋮ Unnamed Item ⋮ When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems ⋮ The fixed initial credit problem for partial-observation energy games is \textsc{Ack}-complete ⋮ Nonelementary Complexities for Branching VASS, MELL, and Extensions ⋮ Separation logics and modalities: a survey ⋮ Lower bounds on the state complexity of population protocols ⋮ Augmenting ATL with strategy contexts ⋮ Modal logics and local quantifiers: a zoo in the elementary hierarchy ⋮ Equivalence of pushdown automata via first-order grammars ⋮ The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings ⋮ Deciding Fast Termination for Probabilistic VASS with Nondeterminism ⋮ The fluted fragment with transitive relations ⋮ Ordinal recursive complexity of unordered data nets ⋮ Unnamed Item ⋮ THE FLUTED FRAGMENT REVISITED ⋮ Unnamed Item ⋮ The ideal view on Rackoff's coverability technique ⋮ On the termination and structural termination problems for counter machines with incrementing errors ⋮ An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning ⋮ Coverability Trees for Petri Nets with Unordered Data ⋮ Canonical Models and the Complexity of Modal Team Logic ⋮ Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence ⋮ An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning ⋮ On a Temporal Logic of Prefixes and Infixes. ⋮ The Parametric Complexity of Lossy Counter Machines ⋮ Unnamed Item ⋮ The Fluted Fragment with Transitivity ⋮ Reachability analysis of low-order discrete state reaction networks obeying conservation laws ⋮ Generalized Post embedding problems

Uses Software

• MONA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A classification of the expressive power of well-structured transition systems
• The most nonelementary theory
• Undecidability of bisimilarity for Petri nets and some related problems
• Linearizing well quasi-orders and bounding the length of bad sequences
• Petri nets and large finite sets
• Ordinal recursive bounds for Higman's theorem
• Ordinal complexity of recursive definitions
• A structure to decide reachability in Petri nets
• The equality problem for vector addition systems is undecidable
• The covering and boundedness problems for vector addition systems
• The typed lambda-calculus is not elementary recursive
• A theory of timed automata
• On the finite containment problem for Petri nets
• Verifying lossy channel systems has nonprimitive recursive complexity.
• Algorithmic analysis of programs with well quasi-ordered domains.
• Complexity bounds for some finite forms of Kruskal's theorem
• Unreliable channels are easier to verify than perfect channels
• Verifying programs with unreliable channels
• On termination and invariance for faulty channel machines
• On pebble automata for data languages with decidable emptiness problem
• Generalized Post embedding problems
• Classes of recursive functions based on Ackermann's function
• The theory of well-quasi-ordering: a frequently discovered concept
• Exact bounds for lengths of reductions in typed λ-calculus
• On Freeze LTL with Ordered Attributes
• The Power of Well-Structured Systems
• Graph Logics with Rational Relations
• Zeno, Hercules and the Hydra: Downward Rational Termination Is Ackermannian
• Alternating register automata on finite words and trees
• LTL with the freeze quantifier and register automata
• Alternating automata on data trees and XPath satisfiability
• Nonelementary Complexities for Branching VASS, MELL, and Extensions
• Relating timed and register automata
• The Ordinal-Recursive Complexity of Timed-arc Petri Nets, Data Nets, and Other Enriched Nets
• Multiply-Recursive Upper Bounds with Higman’s Lemma
• Model Checking Coverability Graphs of Vector Addition Systems
• Proofs and Computations
• Future-Looking Logics on Data Words and Trees
• Classifications of Recursive Functions by Means of Hierarchies
• Classes of Predictably Computable Functions
• Trace Inclusion for One-Counter Nets Revisited
• Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets
• 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
• Senescent ground tree rewrite systems
• Demystifying Reachability in Vector Addition Systems
• History-Register Automata
• The Parametric Ordinal-Recursive Complexity of Post Embedding Problems
• The complexity of decision procedures in relevance logic II
• On the verification problem for weak memory models
• Alternating timed automata
• On the decidability and complexity of Metric Temporal Logic over finite words
• Vector addition system reachability problem
• The ω-Regular Post Embedding Problem
• Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems
• Counter machines and counter languages
• Hierarchies of number-theoretic functions. I
• A classification of the ordinal recursive functions
• The Power of Priority Channel Systems
• Foundations of Software Science and Computation Structures
• Nonprimitive recursive complexity and undecidability for Petri net equivalences
• Well-structured transition systems everywhere!

This page was built for publication: Complexity Hierarchies beyond Elementary