On the public citation graph

Sorting, linear time and the satisfiability problem

0 signed · 91 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.

Claim with ORCID

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.

See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-08342-1_26openalex-snapshot

About the derivation languages of grammars and machines

inferredcites →https://doi.org/10.1007/3-540-51237-3_10openalex-snapshot

Nearly linear time

inferredcites →https://doi.org/10.1007/3-540-54487-9_60openalex-snapshot

RAM with compact memory: a realistic and robust model of computation

inferredcites →https://doi.org/10.1007/3-540-54487-9_68openalex-snapshot

Nontrivial lower bounds for some NP-problems on directed graphs

inferredcites →https://doi.org/10.1007/3-540-56992-8_9openalex-snapshot

The class of problems that are linearly equivalent to satisfiability or a uniform method for proving NP-completeness

inferredcites →https://doi.org/10.1007/978-3-642-69900-9_1openalex-snapshot

Multidimensional Data Structures

inferredcites →https://doi.org/10.1007/978-3-642-69965-8_23openalex-snapshot

Computational Complexity

inferredcites →https://doi.org/10.1007/bf00299636openalex-snapshot

The method of forced enumeration for nondeterministic automata

inferredcites →https://doi.org/10.1007/bf01205055openalex-snapshot

Invariance properties of RAMS and linear time

inferredcites →https://doi.org/10.1007/bf01213861openalex-snapshot

The complexity of on-line simulations between multidimensional turing machines and random access machines

inferredcites →https://doi.org/10.1007/bf01683259openalex-snapshot

New problems complete for nondeterministic log space

inferredcites →https://doi.org/10.1007/bf02090776openalex-snapshot

Power indices and easier hard problems

inferredcites →https://doi.org/10.1007/bf02127799openalex-snapshot

Exact complexity of problems of incompletely specified automata

inferredcites →https://doi.org/10.1007/bfb0022256openalex-snapshot

Monadic logical definability of NP-complete problems

inferredcites →https://doi.org/10.1007/bfb0032027openalex-snapshot

Normalizing and accelerating RAM computations and the problem of reasonable space measures

inferredcites →https://doi.org/10.1016/0020-0190(88)90124-xopenalex-snapshot

LTUR: a simplified linear-time unit resolution algorithm for horn formulae and computer implementation

inferredcites →https://doi.org/10.1016/0020-0190(88)90152-4openalex-snapshot

Short propositional formulas represent nondeterministic computations

inferredcites →https://doi.org/10.1016/0020-0190(90)90133-iopenalex-snapshot

Random access machines with multi-dimensional memories

inferredcites →https://doi.org/10.1016/0020-0190(95)00023-6openalex-snapshot

Unique Horn renaming and Unique 2-Satisfiability

inferredcites →https://doi.org/10.1016/0022-0000(79)90045-xopenalex-snapshot

Fast probabilistic algorithms for hamiltonian circuits and matchings

inferredcites →https://doi.org/10.1016/0096-0551(80)90011-9openalex-snapshot

Introduction to automata theory, languages, and computation

inferredcites →https://doi.org/10.1016/0168-0072(90)90080-lopenalex-snapshot

A uniform method for proving lower bounds on the computational complexity of logical theories

inferredcites →https://doi.org/10.1016/0196-6774(80)90007-3openalex-snapshot

Recognizing disguised NR(1) instances of the satisfiability problem

inferredcites →https://doi.org/10.1016/0304-3975(76)90068-2openalex-snapshot

Complete problems for deterministic polynomial time

inferredcites →https://doi.org/10.1016/0304-3975(91)90177-4openalex-snapshot

An O(T log T) reduction from RAM computations to satisfiability

inferredcites →https://doi.org/10.1016/0304-3975(94)00182-iopenalex-snapshot

The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness

inferredcites →https://doi.org/10.1016/0304-3975(94)90015-9openalex-snapshot

A linear algorithm for renaming a set of clauses as a Horn set

inferredcites →https://doi.org/10.1016/0378-4754(81)90068-9openalex-snapshot

Introduction to automata theory, languages and computation

inferredcites →https://doi.org/10.1016/0743-1066(84)90014-1openalex-snapshot

Linear-time algorithms for testing the satisfiability of propositional horn formulae

inferredcites →https://doi.org/10.1016/0743-1066(87)90014-8openalex-snapshot

Unification as a complexity measure for logic programming

inferredcites →https://doi.org/10.1016/0890-5401(88)90052-1openalex-snapshot

The problem of space invariance for sequential machines

inferredcites →https://doi.org/10.1016/b978-0-444-88071-0.50006-0openalex-snapshot

Machine Models and Simulations

inferredcites →https://doi.org/10.1016/s0022-0000(73)80029-7openalex-snapshot

Time bounded random access machines

inferredcites →https://doi.org/10.1016/s0022-0000(75)80050-xopenalex-snapshot

Space-bounded reducibility among combinatorial problems

inferredcites →https://doi.org/10.1016/s0304-0208(08)73103-7openalex-snapshot

Simulations Among Classes of Random Access Machines and Equivalence Among Numbers Succinctly Represented11A preliminary version of the first part of this paper has been published in the Proceedings of the ACM Symp. on theory of Computation, Milwaukee, 1991.

inferredcites →https://doi.org/10.1016/s0924-6509(09)x7013-3openalex-snapshot

Graphs and Hypergraphs

inferredcites →https://doi.org/10.1038/scientificamerican0984-60openalex-snapshot

Data Structures and Algorithms

inferredcites →https://doi.org/10.1057/jors.1991.155openalex-snapshot

Introduction to Algorithms

inferredcites →https://doi.org/10.1070/rm1981v036n06abeh003102openalex-snapshot

Complexity problems in computational theory

inferredcites →https://doi.org/10.1080/00207168208803302openalex-snapshot

Linear time transformations between combinatorial problems

inferredcites →https://doi.org/10.1090/s0025-5718-1970-0400642-2openalex-snapshot

Table errata: The art of computer programming, Vol. 2: Seminumerical algorithms (Addison-Wesley, Reading, Mass., 1969) by Donald E. Knuth

inferredcites →https://doi.org/10.1109/sfcs.1975.23openalex-snapshot

On time versus space and related problems

inferredcites →https://doi.org/10.1109/sfcs.1983.39openalex-snapshot

On determinism versus non-determinism and related problems

inferredcites →https://doi.org/10.1109/swat.1974.20openalex-snapshot

On the power of multiplication in random access machines

inferredcites →https://doi.org/10.1137/0201010openalex-snapshot

Depth-First Search and Linear Graph Algorithms

inferredcites →https://doi.org/10.1137/0209036openalex-snapshot

Storage Modification Machines

inferredcites →https://doi.org/10.1137/0217005openalex-snapshot

Fast Simulation of Turing Machines by Random Access Machines

inferredcites →https://doi.org/10.1137/0217050openalex-snapshot

A Natural NP-Complete Problem with a Nontrivial Lower Bound

inferredcites →https://doi.org/10.1137/0217058openalex-snapshot

Nondeterministic Space is Closed under Complementation

inferredcites →https://doi.org/10.1137/0219003openalex-snapshot

The Complexity of Very Simple Boolean Formulas with Applications

inferredcites →https://doi.org/10.1137/0219028openalex-snapshot

A Nontrivial Lower Bound for an NP Problem on Automata

inferredcites →https://doi.org/10.1137/s0097539791223206openalex-snapshot

Linear Time Algorithms and NP-Complete Problems

inferredcites →https://doi.org/10.1142/9789812791245openalex-snapshot

Data Structures and Algorithms

inferredcites →https://doi.org/10.1142/s0129054190000217openalex-snapshot

ON THE NOTION OF LINEAR TIME COMPUTABILITY

inferredcites →https://doi.org/10.1145/146637.146666openalex-snapshot

On pointers versus addresses

inferredcites →https://doi.org/10.1145/322003.322015openalex-snapshot

On Time Versus Space

inferredcites →https://doi.org/10.1145/322047.322059openalex-snapshot

Renaming a Set of Clauses as a Horn Set

inferredcites →https://doi.org/10.1145/322047.322060openalex-snapshot

Satisfiability Is Quasilinear Complete in NQL

inferredcites →https://doi.org/10.1145/44483.44492openalex-snapshot

A nonlinear lower bound for random-access machines under logarithmic cost

inferredcites →https://doi.org/10.1145/800133.804350openalex-snapshot

The complexity of satisfiability problems

inferredcites →https://doi.org/10.1145/800157.805047openalex-snapshot

The complexity of theorem-proving procedures

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1006/inco.2001.3084openalex-snapshot

Nonerasing, Counting, and Majority over the Linear Time Hierarchy

inferred← citeshttps://doi.org/10.1006/inco.2002.3027openalex-snapshot

Linear Time and the Power of One First-Order Universal Quantifier

inferred← citeshttps://doi.org/10.1007/10703163_2openalex-snapshot

Descriptive Complexity, Lower Bounds and Linear Time

inferred← citeshttps://doi.org/10.1007/3-540-45793-3_27openalex-snapshot

Local Problems, Planar Local Problems and Linear Time

inferred← citeshttps://doi.org/10.1007/3-540-45841-7_52openalex-snapshot

Generalized Model-Checking over Locally Tree-Decomposable Classes

inferred← citeshttps://doi.org/10.1007/3-540-48168-0_23openalex-snapshot

MonadicNLIN and Quantifier-Free Reductions

inferred← citeshttps://doi.org/10.1007/3-540-49116-3_13openalex-snapshot

A Logical Characterisation of Linear Time on Nondeterministic Turing Machines

inferred← citeshttps://doi.org/10.1007/978-3-540-27836-8_93openalex-snapshot

On the Expressive Power of Monadic Least Fixed Point Logic

inferred← citeshttps://doi.org/10.1007/bf02127799openalex-snapshot

Exact complexity of problems of incompletely specified automata

inferred← citeshttps://doi.org/10.1007/bfb0023481openalex-snapshot

Algebraic and logical characterizations of deterministic linear time classes

inferred← citeshttps://doi.org/10.1007/s00224-019-09937-9openalex-snapshot

Enumeration Complexity of Conjunctive Queries with Functional Dependencies

inferred← citeshttps://doi.org/10.1016/j.jcss.2003.09.002openalex-snapshot

Graph properties checkable in linear time in the number of vertices

inferred← citeshttps://doi.org/10.1016/j.tcs.2004.02.003openalex-snapshot

On unique graph 3-colorability and parsimonious reductions in the plane

inferred← citeshttps://doi.org/10.1016/j.tcs.2005.10.025openalex-snapshot

On the expressive power of monadic least fixed point logic

inferred← citeshttps://doi.org/10.1016/s0304-3975(03)00133-6openalex-snapshot

A descriptive complexity approach to the linear hierarchy

inferred← citeshttps://doi.org/10.1109/sct.1995.514727openalex-snapshot

On superlinear lower bounds in complexity theory

inferred← citeshttps://doi.org/10.1137/s0097539799360240openalex-snapshot

Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time

inferred← citeshttps://doi.org/10.1145/2448496.2448498openalex-snapshot

Enumerating with constant delay the answers to a query

inferred← citeshttps://doi.org/10.1145/2783888.2783894openalex-snapshot

Constant Delay Enumeration for Conjunctive Queries

inferred← citeshttps://doi.org/10.1145/3294052.3319700openalex-snapshot

On the Enumeration Complexity of Unions of Conjunctive Queries

inferred← citeshttps://doi.org/10.1145/3422648.3422655openalex-snapshot

Constant-Delay Enumeration for Nondeterministic Document Spanners

inferred← citeshttps://doi.org/10.1145/3436487openalex-snapshot

Constant-Delay Enumeration for Nondeterministic Document Spanners

inferred← citeshttps://doi.org/10.1145/3452021.3458331openalex-snapshot

Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries

inferred← citeshttps://doi.org/10.1145/3517804.3524166openalex-snapshot

Efficiently Enumerating Answers to Ontology-Mediated Queries

inferred← citeshttps://doi.org/10.1145/3578517openalex-snapshot

Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries

inferred← citeshttps://doi.org/10.1609/aaai.v37i5.25797openalex-snapshot

Efficient Answer Enumeration in Description Logics with Functional Roles

inferred← citeshttps://doi.org/10.2168/lmcs-7(2:20)2011openalex-snapshot

First-order query evaluation on structures of bounded degree

inferred← citeshttps://doi.org/10.4230/lipics.csl.2012.137openalex-snapshot

A Negative Conjunctive Query is Easy if and only if it is Beta-Acyclic

inferred← citeshttps://doi.org/10.4230/lipics.stacs.2014.13openalex-snapshot

A glimpse on constant delay enumeration (Invited Talk)

inferred← citeshttps://doi.org/10.70675/96392143zf2acz4a07z9e6fzc4fe8b6a5b02openalex-snapshot

Query enumeration and nowhere dense graphs

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.