On the public citation graph
Weak monadic second order theory of succesor is not elementary-recursive
0 signed · 182 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.1002/malq.19600060105openalex-snapshot
Weak Second‐Order Arithmetic and Finite Automata
inferredcites →https://doi.org/10.1007/978-1-4613-8928-6_22openalex-snapshot
Weak Second-Order Arithmetic and Finite Automata
inferredcites →https://doi.org/10.1090/s0002-9947-1963-0158822-2openalex-snapshot
Classes of predictably computable functions
inferredcites →https://doi.org/10.1090/s0002-9947-1969-0246760-1openalex-snapshot
Decidability of second-order theories and automata on infinite trees.
inferredcites →https://doi.org/10.1109/focs.1965.11openalex-snapshot
Hierarchies of memory limited computations
inferredcites →https://doi.org/10.1109/swat.1972.29openalex-snapshot
The equivalence problem for regular expressions with squaring requires exponential space
inferredcites →https://doi.org/10.1137/0204006openalex-snapshot
A Decision Procedure for the First Order Theory of Real Addition with Order
inferredcites →https://doi.org/10.1145/321386.321395openalex-snapshot
A Machine-Independent Theory of the Complexity of Recursive Functions
inferredcites →https://doi.org/10.1145/321637.321648openalex-snapshot
On Effective Procedures for Speeding Up Algorithms
inferredcites →https://doi.org/10.1145/800125.804029openalex-snapshot
Word problems requiring exponential time(Preliminary Report)
inferredcites →https://doi.org/10.1145/800125.804033openalex-snapshot
Elementary bounds for presburger arithmetic
inferredcites →https://doi.org/10.1147/rd.32.0114openalex-snapshot
Finite Automata and Their Decision Problems
inferredcites →https://doi.org/10.2307/2269808openalex-snapshot
Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/malq.201400113openalex-snapshot
Locally finite ω‐languages and effective analytic sets have the same topological complexity
inferred← citeshttps://doi.org/10.1007/10722167_11openalex-snapshot
Bounded Model Construction for Monadic Second-Order Logics
inferred← citeshttps://doi.org/10.1007/11944836_21openalex-snapshot
Rational Behaviour and Strategy Construction in Infinite Multiplayer Games
inferred← citeshttps://doi.org/10.1007/3-540-10854-8_49openalex-snapshot
The complexity of automata and subtheories of monadic second order arithmetics
inferred← citeshttps://doi.org/10.1007/3-540-11157-3_27openalex-snapshot
What are the gains of the theory of algorithms
inferred← citeshttps://doi.org/10.1007/3-540-11160-3_4openalex-snapshot
Propositional dynamic logics of programs: A survey
inferred← citeshttps://doi.org/10.1007/3-540-13345-3_43openalex-snapshot
The propositional mu-calculus is elementary
inferred← citeshttps://doi.org/10.1007/3-540-15648-8_27openalex-snapshot
Fixpoints and program looping: Reductions from the Propositional mu-calculus into Propositional Dynamic Logics of Looping
inferred← citeshttps://doi.org/10.1007/3-540-15648-8_7openalex-snapshot
Automata, tableaux, and temporal logics
inferred← citeshttps://doi.org/10.1007/3-540-36596-6_10openalex-snapshot
Cardinality Constraints in Disjunctive Deductive Databases
inferred← citeshttps://doi.org/10.1007/3-540-36596-6_9openalex-snapshot
Automata- and Logic-Based Pattern Languages for Tree-Structured Data
inferred← citeshttps://doi.org/10.1007/3-540-37437-x_7openalex-snapshot
Ineffizienz und Unhandhabbarkeit
inferred← citeshttps://doi.org/10.1007/3-540-40922-x_7openalex-snapshot
B2M: A Semantic Based Tool for BLIF Hardware Descriptions
inferred← citeshttps://doi.org/10.1007/3-540-44685-0_35openalex-snapshot
Extended Temporal Logic Revisited
inferred← citeshttps://doi.org/10.1007/3-540-44802-0_27openalex-snapshot
Decision Procedure for an Extension of WS1S
inferred← citeshttps://doi.org/10.1007/3-540-45061-0_54openalex-snapshot
Monadic Second-Order Logics with Cardinalities
inferred← citeshttps://doi.org/10.1007/3-540-45465-9_64openalex-snapshot
On the Theory of One-Step Rewriting in Trace Monoids
inferred← citeshttps://doi.org/10.1007/3-540-45793-3_21openalex-snapshot
A Logic of Probability with Decidable Model-Checking
inferred← citeshttps://doi.org/10.1007/3-540-56287-7_93openalex-snapshot
Fixed points of Büchi automata
inferred← citeshttps://doi.org/10.1007/3-540-60915-6_3openalex-snapshot
Automated temporal reasoning about reactive systems
inferred← citeshttps://doi.org/10.1007/3-540-61064-2_27openalex-snapshot
Diophantine equations, Presburger arithmetic and finite automata
inferred← citeshttps://doi.org/10.1007/3-540-61511-3_91openalex-snapshot
An improved lower bound for the elementary theories of trees
inferred← citeshttps://doi.org/10.1007/3-540-63174-7_5openalex-snapshot
Implementing WS1S via finite automata
inferred← citeshttps://doi.org/10.1007/978-1-4613-8928-6_4openalex-snapshot
The Role of Büchi’s Automata in Computing Science
inferred← citeshttps://doi.org/10.1007/978-3-031-55601-2_17openalex-snapshot
Semantics of Attack-Defense Trees for Dynamic Countermeasures and a New Hierarchy of Star-Free Languages
inferred← citeshttps://doi.org/10.1007/978-3-032-01475-7_1openalex-snapshot
Formal Languages and Arithmetic Theories: Recent Results and Open Problems
inferred← citeshttps://doi.org/10.1007/978-3-032-04590-4_17openalex-snapshot
On Temporal References via Definite Descriptions in First-Order Monadic Logic of Order
inferred← citeshttps://doi.org/10.1007/978-3-032-04700-7_17openalex-snapshot
On Complementation of Nondeterministic Finite Automata Without Full Determinization
inferred← citeshttps://doi.org/10.1007/978-3-032-33486-2_6openalex-snapshot
A Natural Axiomatization of Büchi Arithmetic
inferred← citeshttps://doi.org/10.1007/978-3-540-30124-0_15openalex-snapshot
The Boundary Between Decidability and Undecidability for Transitive-Closure Logics
inferred← citeshttps://doi.org/10.1007/978-3-540-32254-2_8openalex-snapshot
Solving First-Order Constraints over the Monadic Class
inferred← citeshttps://doi.org/10.1007/978-3-540-69407-6_57openalex-snapshot
Complexity of Aperiodicity for Topological Properties of Regular ω-Languages
inferred← citeshttps://doi.org/10.1007/978-3-540-69850-0_10openalex-snapshot
From Church and Prior to PSL
inferred← citeshttps://doi.org/10.1007/978-3-540-73094-1_19openalex-snapshot
Nets with Tokens Which Carry Data
inferred← citeshttps://doi.org/10.1007/978-3-540-74915-8_5openalex-snapshot
Tightening the Exchange Rates Between Automata
inferred← citeshttps://doi.org/10.1007/978-3-540-78127-1_1openalex-snapshot
From Logic to Theoretical Computer Science – An Update
inferred← citeshttps://doi.org/10.1007/978-3-540-78127-1_36openalex-snapshot
From Monadic Logic to PSL
inferred← citeshttps://doi.org/10.1007/978-3-540-92701-3_7openalex-snapshot
From Philosophical to Industrial Logics
inferred← citeshttps://doi.org/10.1007/978-3-642-04081-8_33openalex-snapshot
Time-Bounded Verification
inferred← citeshttps://doi.org/10.1007/978-3-642-15205-4_34openalex-snapshot
On the Computability of Region-Based Euclidean Logics
inferred← citeshttps://doi.org/10.1007/978-3-642-23217-6_24openalex-snapshot
Parameterized Complexity Results for 1-safe Petri Nets
inferred← citeshttps://doi.org/10.1007/978-3-642-27266-0_7openalex-snapshot
Inefficiency and Intractability
inferred← citeshttps://doi.org/10.1007/978-3-642-37509-5_3openalex-snapshot
Probabilistic XML: Models and Complexity
inferred← citeshttps://doi.org/10.1007/978-3-642-45321-2_5openalex-snapshot
From Löwenheim to PSL and SVA
inferred← citeshttps://doi.org/10.1007/978-3-662-40087-6_1openalex-snapshot
On the Structure of Feasible Computations
inferred← citeshttps://doi.org/10.1007/978-3-662-46681-0_59openalex-snapshot
Nested Antichains for WS1S
inferred← citeshttps://doi.org/10.1007/978-3-662-47666-6_5openalex-snapshot
Provenance Circuits for Trees and Treelike Instances
inferred← citeshttps://doi.org/10.1007/978-3-662-54577-5_24openalex-snapshot
Lazy Automata Techniques for WS1S
inferred← citeshttps://doi.org/10.1007/bf00289117openalex-snapshot
The complexity of combinatorial problems with succinct input representation
inferred← citeshttps://doi.org/10.1007/bf01084283openalex-snapshot
Complexity of algorithms and computations
inferred← citeshttps://doi.org/10.1007/bf01683261openalex-snapshot
On the complexity of finite, pushdown, and stack automata
inferred← citeshttps://doi.org/10.1007/bf01744435openalex-snapshot
A note on the complexity of program evaluation
inferred← citeshttps://doi.org/10.1007/bf02104744openalex-snapshot
Complexity lower bounds for machine computing models
inferred← citeshttps://doi.org/10.1007/bf02127803openalex-snapshot
Logic, semigroups and automata on words
inferred← citeshttps://doi.org/10.1007/bf02460939openalex-snapshot
Limits on the computing power of biological systems
inferred← citeshttps://doi.org/10.1007/bfb0015772openalex-snapshot
The complementation problem for Büchi automata with applications to temporal logic
inferred← citeshttps://doi.org/10.1007/bfb0028022openalex-snapshot
Mona & Fido: The logic-automaton connection in practice
inferred← citeshttps://doi.org/10.1007/bfb0031382openalex-snapshot
Implementing WS1S via finite automata: Performance issues
inferred← citeshttps://doi.org/10.1007/s00153-008-0101-7openalex-snapshot
Topological complexity of locally finite ω-languages
inferred← citeshttps://doi.org/10.1007/s00224-018-9901-2openalex-snapshot
Evaluating Datalog via Tree Automata and Cycluits
inferred← citeshttps://doi.org/10.1007/s00778-009-0150-5openalex-snapshot
Query evaluation over probabilistic XML
inferred← citeshttps://doi.org/10.1016/0022-0000(78)90021-1openalex-snapshot
A 222pn upper bound on the complexity of Presburger Arithmetic
inferred← citeshttps://doi.org/10.1016/0022-0000(80)90027-6openalex-snapshot
Complexity results for classes of quantificational formulas
inferred← citeshttps://doi.org/10.1016/0022-0000(82)90003-4openalex-snapshot
Process logic: Expressiveness, decidability, completeness
inferred← citeshttps://doi.org/10.1016/0022-0000(86)90026-7openalex-snapshot
Automata-theoretic techniques for modal logics of programs
inferred← citeshttps://doi.org/10.1016/0168-0072(90)90080-lopenalex-snapshot
A uniform method for proving lower bounds on the computational complexity of logical theories
inferred← citeshttps://doi.org/10.1016/0304-3975(87)90008-9openalex-snapshot
The complementation problem for Büchi automata with applications to temporal logic
inferred← citeshttps://doi.org/10.1016/0304-3975(95)00221-9openalex-snapshot
Exact complexity bounds for ordinal addition
inferred← citeshttps://doi.org/10.1016/0890-5401(89)90031-xopenalex-snapshot
An automata theoretic decision procedure for the propositional mu-calculus
inferred← citeshttps://doi.org/10.1016/b978-0-12-800160-8.00005-xopenalex-snapshot
Classifying Problems into Complexity Classes
inferred← citeshttps://doi.org/10.1016/b978-0-444-88071-0.50007-2openalex-snapshot
A Catalog of Complexity Classes
inferred← citeshttps://doi.org/10.1016/b978-0-444-88074-1.50021-4openalex-snapshot
Temporal and Modal Logic
inferred← citeshttps://doi.org/10.1016/j.apal.2005.12.009openalex-snapshot
A nonasymptotic lower time bound for a strictly bounded second-order arithmetic
inferred← citeshttps://doi.org/10.1016/j.datak.2006.11.003openalex-snapshot
Deciding XPath containment with MSO
inferred← citeshttps://doi.org/10.1016/j.entcs.2004.05.013openalex-snapshot
On Decidability Properties of Local Sentences
inferred← citeshttps://doi.org/10.1016/j.entcs.2009.08.028openalex-snapshot
A Practical Approach to Courcelle's Theorem
inferred← citeshttps://doi.org/10.1016/j.ic.2004.02.002openalex-snapshot
The most nonelementary theory
inferred← citeshttps://doi.org/10.1016/j.ic.2006.01.005openalex-snapshot
A Kleene theorem and model checking algorithms for existentially bounded communicating automata
inferred← citeshttps://doi.org/10.1016/j.ic.2007.01.002openalex-snapshot
Inverse monoids: Decidability and complexity of algebraic questions
inferred← citeshttps://doi.org/10.1016/j.ic.2010.07.003openalex-snapshot
Ehrenfeucht–Fraïssé goes automatic for real addition
inferred← citeshttps://doi.org/10.1016/j.jcss.2014.04.014openalex-snapshot
Bounded-width QBF is PSPACE-complete
inferred← citeshttps://doi.org/10.1016/j.jlamp.2015.11.002openalex-snapshot
Incremental reasoning on monadic second-order logics with logic programming
inferred← citeshttps://doi.org/10.1016/j.jlamp.2016.02.005openalex-snapshot
Logic programming approach to automata-based decision procedures
inferred← citeshttps://doi.org/10.1016/j.jlap.2006.12.001openalex-snapshot
A logic of reachable patterns in linked data-structures
inferred← citeshttps://doi.org/10.1016/j.tcs.2006.08.004openalex-snapshot
On decidability properties of local sentences
inferred← citeshttps://doi.org/10.1016/j.tcs.2015.04.033openalex-snapshot
A link between multioperator and tree valuation automata and logics
inferred← citeshttps://doi.org/10.1016/s0019-9958(77)90443-0openalex-snapshot
Application of model theoretic games to discrete linear orders and finite automata
inferred← citeshttps://doi.org/10.1016/s0019-9958(82)91258-xopenalex-snapshot
Propositional dynamic logic of looping and converse is elementarily decidable
inferred← citeshttps://doi.org/10.1016/s0019-9958(83)80051-5openalex-snapshot
Temporal logic can be more expressive
inferred← citeshttps://doi.org/10.1016/s0019-9958(84)80047-9openalex-snapshot
Deciding full branching time logic
inferred← citeshttps://doi.org/10.1016/s0022-0000(03)00005-9openalex-snapshot
The complexity of the temporal logic with “until” over general linear time
inferred← citeshttps://doi.org/10.1016/s0022-0000(76)80035-9openalex-snapshot
Polynomial and abstract subrecursive classes
inferred← citeshttps://doi.org/10.1016/s0049-237x(08)71253-9openalex-snapshot
The Role of Finite Automata in the Development of Modern Computing Theory*
inferred← citeshttps://doi.org/10.1016/s0049-237x(08)71820-2openalex-snapshot
Decision Problems in Predicate Logic
inferred← citeshttps://doi.org/10.1016/s0049-237x(09)70440-9openalex-snapshot
Bounded Concatenation Theory as a Uniform Method for Proving Lower Complexity Bounds
inferred← citeshttps://doi.org/10.1016/s0168-0072(97)00005-5openalex-snapshot
Ehrenfeucht games and ordinal addition
inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00349-8openalex-snapshot
wMSO theories as grammar formalisms
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00089-0openalex-snapshot
Decision procedures for inductive Boolean functions based on alternating automata
inferred← citeshttps://doi.org/10.1016/s1570-8683(03)00008-9openalex-snapshot
Mathematical modal logic: A view of its evolution
inferred← citeshttps://doi.org/10.1017/s0022481200051136openalex-snapshot
On the complexity of the theories of weak direct powers
inferred← citeshttps://doi.org/10.1017/s1471068414000660openalex-snapshot
Decidability of the Clark's completion semantics for monadic programs and queries
inferred← citeshttps://doi.org/10.1070/rm1978v033n02abeh002304openalex-snapshot
DECIDABILITY PROBLEMS OF EXTENDED THEORIES
inferred← citeshttps://doi.org/10.1070/rm1981v036n06abeh003102openalex-snapshot
Complexity problems in computational theory
inferred← citeshttps://doi.org/10.1088/1742-6596/1202/1/012018openalex-snapshot
On computational complexity of successor theory with unary transitive closure
inferred← citeshttps://doi.org/10.1090/dimacs/031/05openalex-snapshot
Why is modal logic so robustly decidable?
inferred← citeshttps://doi.org/10.1093/logcom/exl004openalex-snapshot
A Logic of Probability with Decidable Model Checking
inferred← citeshttps://doi.org/10.1093/logcom/exn056openalex-snapshot
Fixpoint and While Temporal Query Languages
inferred← citeshttps://doi.org/10.1109/lics.2006.25openalex-snapshot
Fixed-Parameter Hierarchies inside PSPACE
inferred← citeshttps://doi.org/10.1109/sfcs.1978.9openalex-snapshot
Complexity of solvable cases of the decision problem for the predicate calculus
inferred← citeshttps://doi.org/10.1109/sfcs.1980.35openalex-snapshot
Process logic: Expressiveness, decidability, completeness
inferred← citeshttps://doi.org/10.1109/sfcs.1983.51openalex-snapshot
Reasoning about infinite computation paths
inferred← citeshttps://doi.org/10.1109/time.2005.35openalex-snapshot
Temporal Query Languages Expressive Power: µTL versus T-WHILE
inferred← citeshttps://doi.org/10.1137/0214066openalex-snapshot
Equations between Regular Terms and an Application to Process Logic
inferred← citeshttps://doi.org/10.1142/9789814271059_0002openalex-snapshot
Finite-State Automata on Infinite Inputs
inferred← citeshttps://doi.org/10.1145/1142351.1142382openalex-snapshot
Processing queries on tree-structured data efficiently
inferred← citeshttps://doi.org/10.1145/1182613.1182618openalex-snapshot
Logical characterizations of heap abstractions
inferred← citeshttps://doi.org/10.1145/1283920.1283938openalex-snapshot
An overview of computational complexity
inferred← citeshttps://doi.org/10.1145/129712.129739openalex-snapshot
Exponential determinization for ω-automata with strong-fairness acceptance condition (extended abstract)
inferred← citeshttps://doi.org/10.1145/1559795.1559831openalex-snapshot
Running tree automata on probabilistic XML
inferred← citeshttps://doi.org/10.1145/22145.22173openalex-snapshot
Improved upper and lower bounds for modal logics of programs
inferred← citeshttps://doi.org/10.1145/2858784openalex-snapshot
Complexity Hierarchies beyond Elementary
inferred← citeshttps://doi.org/10.1145/321832.321840openalex-snapshot
On Almost Everywhere Complex Recursive Functions
inferred← citeshttps://doi.org/10.1145/321892.321895openalex-snapshot
On Reducibility to Complex or Sparse Sets
inferred← citeshttps://doi.org/10.1145/3294052.3319702openalex-snapshot
Enumeration on Trees with Tractable Combined Complexity and Efficient Updates
inferred← citeshttps://doi.org/10.1145/358141.358144openalex-snapshot
An overview of computational complexity
inferred← citeshttps://doi.org/10.1145/361227.361231openalex-snapshot
The intrinsically exponential complexity of the circularity problem for attribute grammars
inferred← citeshttps://doi.org/10.1145/3680410openalex-snapshot
On Program Synthesis and Large Language Models
inferred← citeshttps://doi.org/10.1145/375551.375569openalex-snapshot
Extended path expressions of XML
inferred← citeshttps://doi.org/10.1145/378795.378851openalex-snapshot
The pointer assertion logic engine
inferred← citeshttps://doi.org/10.1145/602220.602223openalex-snapshot
Cosmological lower bound on the circuit complexity of a small problem in logic
inferred← citeshttps://doi.org/10.1145/800057.808711openalex-snapshot
Automata theoretic techniques for modal logics of programs
inferred← citeshttps://doi.org/10.1145/800076.802492openalex-snapshot
Propositional Dynamic Logic of looping and converse
inferred← citeshttps://doi.org/10.1145/800119.803885openalex-snapshot
Computational parallels between the regular and context-free languages
inferred← citeshttps://doi.org/10.1145/800119.803894openalex-snapshot
On the complexity of the theories of weak direct products (Preliminary Report)
inferred← citeshttps://doi.org/10.1145/800119.803895openalex-snapshot
Structure of complexity in the weak monadic second-order theories of the natural numbers
inferred← citeshttps://doi.org/10.1145/800125.804033openalex-snapshot
Elementary bounds for presburger arithmetic
inferred← citeshttps://doi.org/10.13140/rg.2.2.32511.36005openalex-snapshot
TEMPORAL CONTROLLED NATURAL LANGUAGE FOR FORMAL SPECIFICATION
inferred← citeshttps://doi.org/10.2178/jsl/1318338854openalex-snapshot
Automatic structures of bounded degree revisited
inferred← citeshttps://doi.org/10.22024/unikent/01.02.86456openalex-snapshot
Verification of real-time systems: improving tool support
inferred← citeshttps://doi.org/10.2307/2273858openalex-snapshot
Classifying the computational complexity of problems
inferred← citeshttps://doi.org/10.2307/2275735openalex-snapshot
The theory of integer multiplication with order restricted to primes is decidable
inferred← citeshttps://doi.org/10.3166/jancl.14.105-148openalex-snapshot
PITL2MONA: Implementing a Decision Procedure for Propositional Interval Temporal Logic
inferred← citeshttps://doi.org/10.32523/2077-9879-2022-13-1-44-68openalex-snapshot
The Recognition Complexity of Decidable Theories
inferred← citeshttps://doi.org/10.48550/arxiv.1301.5139openalex-snapshot
The Tree Width of Separation Logic with Recursive Definitions
inferred← citeshttps://doi.org/10.48550/arxiv.1701.06282openalex-snapshot
Lazy Automata Techniques for WS1S
inferred← citeshttps://doi.org/10.5821/dissertation-2117-94931openalex-snapshot
On the complexity of resolution-based proof systems
inferred← citeshttps://doi.org/10.5860/choice.48-6328openalex-snapshot
Foundations of XML processing: the tree-automata approach
inferred← citeshttps://doi.org/10.70675/0060a957z6f8ez44e2z9a5dze9b2f3193fcbopenalex-snapshot
Logiques de séparation : complexité, expressivité, calculs
inferred← citeshttps://doi.org/10.70675/0403fec7z6d88z4f5czb5d8z53294519fb37openalex-snapshot
Automated reasoning on trees with cardinality constraints
inferred← citeshttps://doi.org/10.70675/150e8dfdz60abz447bzad32z6b94f3f90094openalex-snapshot
Strategy complexity of zero-sum games on graphs
inferred← citeshttps://doi.org/10.70675/86b37144z3689z4cedzb5aez3b420a78f57dopenalex-snapshot
Combined complexity of probabilistic query evaluation
inferred← citeshttps://doi.org/10.70675/bc873801z115cz462az9be1z279446b155a9openalex-snapshot
Automatic synthesis of systems with data
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.