On the public citation graph
Complexity Hierarchies beyond Elementary
0 signed · 161 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1006/inco.1996.0003openalex-snapshot
Unreliable Channels Are Easier to Verify Than Perfect Channels
inferredcites →https://doi.org/10.1006/inco.1996.0053openalex-snapshot
Verifying Programs with Unreliable Channels
inferredcites →https://doi.org/10.1006/inco.1999.2843openalex-snapshot
Algorithmic Analysis of Programs with Well Quasi-ordered Domains
inferredcites →https://doi.org/10.1006/jsco.1994.1059openalex-snapshot
Complexity Bounds for Some Finite Forms of Kruskal's Theorem
inferredcites →https://doi.org/10.1007/11690634_15openalex-snapshot
On Metric Temporal Logic and Faulty Turing Machines
inferredcites →https://doi.org/10.1007/3-540-18088-5_43openalex-snapshot
A generalization of the procedure of karp and miller to well structured transition systems
inferredcites →https://doi.org/10.1007/978-3-319-11439-2_12openalex-snapshot
Trace Inclusion for One-Counter Nets Revisited
inferredcites →https://doi.org/10.1007/978-3-540-77050-3_22openalex-snapshot
Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems
inferredcites →https://doi.org/10.1007/978-3-540-78499-9_8openalex-snapshot
The ω-Regular Post Embedding Problem
inferredcites →https://doi.org/10.1007/978-3-642-03816-7_29openalex-snapshot
Future-Looking Logics on Data Words and Trees
inferredcites →https://doi.org/10.1007/978-3-642-15155-2_54openalex-snapshot
Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets
inferredcites →https://doi.org/10.1007/978-3-642-22012-8_35openalex-snapshot
Multiply-Recursive Upper Bounds with Higman’s Lemma
inferredcites →https://doi.org/10.1007/978-3-642-22993-0_13openalex-snapshot
Model Checking Coverability Graphs of Vector Addition Systems
inferredcites →https://doi.org/10.1007/978-3-642-30642-6_22openalex-snapshot
Cutting through Regular Post Embedding Problems
inferredcites →https://doi.org/10.1007/978-3-642-37075-5_18openalex-snapshot
The Parametric Ordinal-Recursive Complexity of Post Embedding Problems
inferredcites →https://doi.org/10.1007/978-3-642-37075-5_2openalex-snapshot
History-Register Automata
inferredcites →https://doi.org/10.1007/978-3-642-40184-8_2openalex-snapshot
The Power of Well-Structured Systems
inferredcites →https://doi.org/10.1007/978-3-642-40313-2_57openalex-snapshot
Zeno, Hercules and the Hydra: Downward Rational Termination Is Ackermannian
inferredcites →https://doi.org/10.1007/bf01694011openalex-snapshot
Counter machines and counter languages
inferredcites →https://doi.org/10.1007/bf01967649openalex-snapshot
Hierarchies of number-theoretic functions. I
inferredcites →https://doi.org/10.1007/bf01973619openalex-snapshot
A classification of the ordinal recursive functions
inferredcites →https://doi.org/10.1007/bf01995674openalex-snapshot
Specifying real-time properties with metric temporal logic
inferredcites →https://doi.org/10.1007/bfb0028773openalex-snapshot
MONA 1.x: New techniques for WS1S and WS2S
inferredcites →https://doi.org/10.1007/bfb0064872openalex-snapshot
Weak monadic second order theory of succesor is not elementary-recursive
inferredcites →https://doi.org/10.1007/s00165-012-0234-7openalex-snapshot
On termination and invariance for faulty channel machines
inferredcites →https://doi.org/10.1016/0097-3165(72)90063-5openalex-snapshot
The theory of well-quasi-ordering: A frequently discovered concept
inferredcites →https://doi.org/10.1016/0304-3975(76)90008-6openalex-snapshot
The equality problem for vector addition systems is undecidable
inferredcites →https://doi.org/10.1016/0304-3975(78)90036-1openalex-snapshot
The covering and boundedness problems for vector addition systems
inferredcites →https://doi.org/10.1016/0304-3975(79)90007-0openalex-snapshot
The typed λ-calculus is not elementary recursive
inferredcites →https://doi.org/10.1016/0304-3975(84)90029-xopenalex-snapshot
Petri nets and large finite sets
inferredcites →https://doi.org/10.1016/0304-3975(92)90173-dopenalex-snapshot
A structure to decide reachability in Petri nets
inferredcites →https://doi.org/10.1016/0304-3975(94)90010-8openalex-snapshot
A theory of timed automata
inferredcites →https://doi.org/10.1016/0304-3975(95)00037-wopenalex-snapshot
Undecidability of bisimilarity for Petri nets and some related problems
inferredcites →https://doi.org/10.1016/0890-5401(92)90027-dopenalex-snapshot
Ordinal complexity of recursive definitions
inferredcites →https://doi.org/10.1016/1385-7258(77)90067-1openalex-snapshot
Well-partial orderings and hierarchies
inferredcites →https://doi.org/10.1016/j.apal.2007.02.004openalex-snapshot
Classifying the phase transition threshold for Ackermannian functions
inferredcites →https://doi.org/10.1016/j.ic.2004.02.002openalex-snapshot
The most nonelementary theory
inferredcites →https://doi.org/10.1016/j.ic.2010.11.003openalex-snapshot
A classification of the expressive power of well-structured transition systems
inferredcites →https://doi.org/10.1016/j.jcss.2010.03.004openalex-snapshot
On pebble automata for data languages with decidable emptiness problem
inferredcites →https://doi.org/10.1016/j.tcs.2015.07.012openalex-snapshot
Linearizing well quasi-orders and bounding the length of bad sequences
inferredcites →https://doi.org/10.1016/s0020-0190(01)00337-4openalex-snapshot
Verifying lossy channel systems has nonprimitive recursive complexity
inferredcites →https://doi.org/10.1016/s0049-237x(09)70143-0openalex-snapshot
Complexity of Normalization in the Pure Typed Lambda – Calculus
inferredcites →https://doi.org/10.1016/s0049-237x(98)80018-9openalex-snapshot
Hierarchies of Provably Recursive Functions
inferredcites →https://doi.org/10.1016/s0049-237x(99)80033-0openalex-snapshot
Computation Models and Function Algebras
inferredcites →https://doi.org/10.1016/s0304-3975(00)00100-6openalex-snapshot
Nonprimitive recursive complexity and undecidability for Petri net equivalences
inferredcites →https://doi.org/10.1016/s0304-3975(00)00102-xopenalex-snapshot
Well-structured transition systems everywhere!
inferredcites →https://doi.org/10.1016/s0304-3975(97)00009-1openalex-snapshot
Ordinal recursive bounds for Higman's theorem
inferredcites →https://doi.org/10.1017/s0960129514000322openalex-snapshot
Relating timed and register automata
inferredcites →https://doi.org/10.1090/s0002-9947-1962-0142453-3openalex-snapshot
Classifications of Recursive Functions by Means of Hierarchies
inferredcites →https://doi.org/10.1090/s0002-9947-1963-0158822-2openalex-snapshot
Classes of predictably computable functions
inferredcites →https://doi.org/10.1109/lics.2008.47openalex-snapshot
The Ordinal Recursive Complexity of Lossy Channel Systems
inferredcites →https://doi.org/10.1109/lics.2011.39openalex-snapshot
Ackermannian and Primitive-Recursive Bounds with Dickson's Lemma
inferredcites →https://doi.org/10.1109/lics.2012.46openalex-snapshot
The Ordinal-Recursive Complexity of Timed-arc Petri Nets, Data Nets, and Other Enriched Nets
inferredcites →https://doi.org/10.1109/lics.2015.16openalex-snapshot
Demystifying Reachability in Vector Addition Systems
inferredcites →https://doi.org/10.1145/115234.115351openalex-snapshot
A propositional modal logic of time intervals
inferredcites →https://doi.org/10.1145/1507244.1507246openalex-snapshot
LTL with the freeze quantifier and register automata
inferredcites →https://doi.org/10.1145/1706299.1706303openalex-snapshot
On the verification problem for weak memory models
inferredcites →https://doi.org/10.1145/1926385.1926421openalex-snapshot
Vector addition system reachability problem
inferredcites →https://doi.org/10.1145/1929954.1929956openalex-snapshot
Alternating automata on data trees and XPath satisfiability
inferredcites →https://doi.org/10.1145/2603088.2603112openalex-snapshot
Senescent ground tree rewrite systems
inferredcites →https://doi.org/10.1145/2733375openalex-snapshot
Nonelementary Complexities for Branching VASS, MELL, and Extensions
inferredcites →https://doi.org/10.1145/322261.322271openalex-snapshot
The Complexity of the Finite Containment Problem for Petri Nets
inferredcites →https://doi.org/10.1145/800070.802201openalex-snapshot
Decidability of reachability in vector addition systems (Preliminary Version)
inferredcites →https://doi.org/10.1145/800076.802477openalex-snapshot
An algorithm for the general Petri net reachability problem
inferredcites →https://doi.org/10.1145/800125.804029openalex-snapshot
Word problems requiring exponential time(Preliminary Report)
inferredcites →https://doi.org/10.1145/800196.806014openalex-snapshot
The complexity of loop programs
inferredcites →https://doi.org/10.2140/pjm.1965.15.1027openalex-snapshot
Classes of recursive functions based on Ackermann’s function
inferredcites →https://doi.org/10.2168/lmcs-10(4:4)2014openalex-snapshot
The Power of Priority Channel Systems
inferredcites →https://doi.org/10.2168/lmcs-3(1:8)2007openalex-snapshot
On the decidability and complexity of Metric Temporal Logic over finite words
inferredcites →https://doi.org/10.2168/lmcs-8(1:22)2012openalex-snapshot
Alternating register automata on finite words and trees
inferredcites →https://doi.org/10.2168/lmcs-9(3:1)2013openalex-snapshot
Graph Logics with Rational Relations
inferredcites →https://doi.org/10.2307/2274261openalex-snapshot
The undecidability of entailment and relevant implication
inferredcites →https://doi.org/10.2307/2586811openalex-snapshot
The complexity of decision procedures in relevance logic II
inferredcites →https://doi.org/10.2307/2695106openalex-snapshot
Exact bounds for lengths of reductions in typed λ-calculus
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/978-3-030-19570-0_45openalex-snapshot
Axiomatising Logics with Separating Conjunction and Modalities
inferred← citeshttps://doi.org/10.1007/978-3-030-30229-0_3openalex-snapshot
The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings
inferred← citeshttps://doi.org/10.1007/978-3-030-31784-3_27openalex-snapshot
Deciding Fast Termination for Probabilistic VASS with Nondeterminism
inferred← citeshttps://doi.org/10.1007/978-3-030-45231-5_24openalex-snapshot
An Auxiliary Logic on Trees: on the Tower-Hardness of Logics Featuring Reachability and Submodel Reasoning
inferred← citeshttps://doi.org/10.1007/978-3-030-99253-8_16openalex-snapshot
Modal Logics and Local Quantifiers: A Zoo in the Elementary Hierarchy
inferred← citeshttps://doi.org/10.1007/978-3-031-57228-9_1openalex-snapshot
Ackermannian Completion of Separators
inferred← citeshttps://doi.org/10.1007/978-3-031-57231-9openalex-snapshot
Foundations of Software Science and Computation Structures
inferred← citeshttps://doi.org/10.1007/978-3-031-57231-9_12openalex-snapshot
Parameterized Broadcast Networks with Registers: from NP to the Frontiers of Decidability
inferred← citeshttps://doi.org/10.1007/978-3-031-97548-6_7openalex-snapshot
Linear Recurrence Sequence Automata and the Addition of Abstract Numeration Systems
inferred← citeshttps://doi.org/10.1007/978-3-319-51046-0_8openalex-snapshot
What Makes Petri Nets Harder to Verify: Stack or Data?
inferred← citeshttps://doi.org/10.1007/978-3-662-73305-9_5openalex-snapshot
The Reachability Problem in Petri Nets: Decidability and Hardness
inferred← citeshttps://doi.org/10.1007/s00446-023-00450-4openalex-snapshot
Lower bounds on the state complexity of population protocols
inferred← citeshttps://doi.org/10.1016/j.apal.2021.103042openalex-snapshot
The fluted fragment with transitive relations
inferred← citeshttps://doi.org/10.1016/j.ic.2017.02.002openalex-snapshot
Ordinal recursive complexity of Unordered Data Nets
inferred← citeshttps://doi.org/10.1016/j.ic.2020.104582openalex-snapshot
The ideal view on Rackoff's coverability technique
inferred← citeshttps://doi.org/10.1016/j.ipl.2016.10.005openalex-snapshot
The fixed initial credit problem for partial-observation energy games is Ack-complete
inferred← citeshttps://doi.org/10.1016/j.jcss.2019.10.002openalex-snapshot
Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence
inferred← citeshttps://doi.org/10.1016/j.jcss.2020.07.004openalex-snapshot
Equivalence of pushdown automata via first-order grammars
inferred← citeshttps://doi.org/10.1016/j.jcss.2021.03.007openalex-snapshot
On the termination and structural termination problems for counter machines with incrementing errors
inferred← citeshttps://doi.org/10.1016/j.jpdc.2021.11.008openalex-snapshot
Reachability in parallel programs is polynomial in the number of threads
inferred← citeshttps://doi.org/10.1016/j.tcs.2016.04.020openalex-snapshot
Forward analysis and model checking for trace bounded WSTS
inferred← citeshttps://doi.org/10.1016/j.tcs.2025.115546openalex-snapshot
Tight length theorems for multiset extensions of Higman’s lemma
inferred← citeshttps://doi.org/10.1093/logcom/exab016openalex-snapshot
Internal proof calculi for modal logics with separating conjunction
inferred← citeshttps://doi.org/10.1093/logcom/exz019openalex-snapshot
The power of modal separation logics
inferred← citeshttps://doi.org/10.1093/oso/9780192867964.001.0001openalex-snapshot
Fragments of First-Order Logic
inferred← citeshttps://doi.org/10.1093/oso/9780192867964.003.0007openalex-snapshot
Counting with one variable
inferred← citeshttps://doi.org/10.1093/oso/9780192867964.003.0008openalex-snapshot
Counting with two variables
inferred← citeshttps://doi.org/10.1093/oso/9780192867964.003.0013openalex-snapshot
Equivalence and counting
inferred← citeshttps://doi.org/10.1109/access.2026.3725439openalex-snapshot
Gandy Direct-Limit Theorem: Polynomial-Time Prediction on Operator-Generated Networks
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00120openalex-snapshot
Reachability in Vector Addition Systems is Ackermann-complete
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00121openalex-snapshot
The Reachability Problem for Petri Nets is Not Primitive Recursive
inferred← citeshttps://doi.org/10.1109/lics.2017.8005101openalex-snapshot
Polynomial automata: Zeroness and applications
inferred← citeshttps://doi.org/10.1109/lics.2019.8785656openalex-snapshot
Why Propositional Quantification Makes Modal Logics on Trees Robustly Hard?
inferred← citeshttps://doi.org/10.1109/lics.2019.8785796openalex-snapshot
Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension
inferred← citeshttps://doi.org/10.1109/lics.2019.8785848openalex-snapshot
Bisimulation Equivalence of First-Order Grammars is ACKERMANN-Complete
inferred← citeshttps://doi.org/10.1109/lics52264.2021.9470733openalex-snapshot
Decidability and Complexity in Weakening and Contraction Hypersequent Substructural Logics
inferred← citeshttps://doi.org/10.1109/lics56636.2023.10175824openalex-snapshot
The Logic of Prefixes and Suffixes is Elementary under Homogeneity*
inferred← citeshttps://doi.org/10.1109/lics65433.2025.00050openalex-snapshot
Reachability and Related Problems in Vector Addition Systems with Nested Zero Tests
inferred← citeshttps://doi.org/10.1109/pdcat46702.2019.00078openalex-snapshot
Reachability in Multithreaded Programs Is Polynomial in the Number of Threads
inferred← citeshttps://doi.org/10.1109/synasc54541.2021.00042openalex-snapshot
Towards the Complexity of Petri Nets and One Counter Machines via Coordinated Table Selective Substitution Systems
inferred← citeshttps://doi.org/10.1134/s1995080226617157openalex-snapshot
Weak Jumps in the Elementary Degrees and Jump Inversion Theorems
inferred← citeshttps://doi.org/10.1137/20m1383471openalex-snapshot
When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1145/2733375openalex-snapshot
Nonelementary Complexities for Branching VASS, MELL, and Extensions
inferred← citeshttps://doi.org/10.1145/2893582.2893585openalex-snapshot
The complexity of reachability in vector addition systems
inferred← citeshttps://doi.org/10.1145/2933575.2933593openalex-snapshot
The Complexity of Coverability in ν-Petri Nets
inferred← citeshttps://doi.org/10.1145/3209108.3209191openalex-snapshot
Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS
inferred← citeshttps://doi.org/10.1145/3212019.3212021openalex-snapshot
Satisfiability of Xpath on data trees
inferred← citeshttps://doi.org/10.1145/3309760openalex-snapshot
Synchronizing Data Words for Register Automata
inferred← citeshttps://doi.org/10.1145/3313276.3316369openalex-snapshot
The Reachability Problem for Petri Nets Is Not Elementary
inferred← citeshttps://doi.org/10.1145/3373718.3394753openalex-snapshot
Complexity of controlled bad sequences over finite sets of Nd
inferred← citeshttps://doi.org/10.1145/3464794openalex-snapshot
The Reachability Problem for Two-Dimensional Vector Addition Systems with States
inferred← citeshttps://doi.org/10.1145/3465084.3467912openalex-snapshot
Lower Bounds on the State Complexity of Population Protocols
inferred← citeshttps://doi.org/10.1145/3531130.3533357openalex-snapshot
Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes
inferred← citeshttps://doi.org/10.1145/3569954openalex-snapshot
On Composing Finite Forests with Modal Logics
inferred← citeshttps://doi.org/10.1145/3661814.3662086openalex-snapshot
Soundness of reset workflow nets
inferred← citeshttps://doi.org/10.1145/3661814.3662116openalex-snapshot
On the Separability Problem of VASS Reachability Languages
inferred← citeshttps://doi.org/10.1145/3717823.3718149openalex-snapshot
Reachability in One-Dimensional Pushdown Vector Addition Systems Is Decidable
inferred← citeshttps://doi.org/10.1145/3808281openalex-snapshot
Towards Efficient Matching of Regexes with Backreferences using Register Set Automata
inferred← citeshttps://doi.org/10.1145/3832064.3832068openalex-snapshot
On Determinizability of Tropical Weighted Automata
inferred← citeshttps://doi.org/10.1155/2019/1035974openalex-snapshot
Reachability Analysis of Low‐Order Discrete State Reaction Networks Obeying Conservation Laws
inferred← citeshttps://doi.org/10.26907/2949-3919.2024.2.47-69openalex-snapshot
Punctual categoricity and a jump operation in the primitive recursive degrees
inferred← citeshttps://doi.org/10.4204/eptcs.346.12openalex-snapshot
Adding the Relation Meets to the Temporal Logic of Prefixes and Infixes makes it EXPSPACE-Complete
inferred← citeshttps://doi.org/10.46298/lmcs-18(3:5)2022openalex-snapshot
Why Does Propositional Quantification Make Modal and Temporal Logics on Trees Robustly Hard?
inferred← citeshttps://doi.org/10.46298/lmcs-20(1:23)2024openalex-snapshot
The addition of temporal neighborhood makes the logic of prefixes and sub-intervals EXPSPACE-complete
inferred← citeshttps://doi.org/10.63331/upalaw/32/03openalex-snapshot
From Context-Free Languages to Mildly Context-Sensitive Languages Complexity Views
inferred← citeshttps://doi.org/10.70675/0060a957z6f8ez44e2z9a5dze9b2f3193fcbopenalex-snapshot
Logiques de séparation : complexité, expressivité, calculs
inferred← citeshttps://doi.org/10.70675/4a9c5939z993ez4410z9831z9f7dfc3b2346openalex-snapshot
Semantics of Strategy Logic
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.