On the public citation graph

On non-determinancy in simple computing devices

https://doi.org/10.1007/bf00289513
0 signed · 113 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/bf01694180openalex-snapshot
Computational complexity of random access stored program machines
inferredcites →https://doi.org/10.1007/bf02759719openalex-snapshot
Real time computation
inferredcites →https://doi.org/10.1016/0020-0271(67)90007-1openalex-snapshot
The mathematical theory of context-free languages
inferredcites →https://doi.org/10.1090/s0002-9947-1965-0170805-7openalex-snapshot
On the Computational Complexity of Algorithms
inferredcites →https://doi.org/10.1109/focs.1965.11openalex-snapshot
Hierarchies of memory limited computations
inferredcites →https://doi.org/10.1145/321356.321362openalex-snapshot
Two-Tape Simulation of Multitape Turing Machines
inferredcites →https://doi.org/10.1145/321650.321661openalex-snapshot
An Overview of the Theory of Computational Complexity
inferredcites →https://doi.org/10.13182/nse70-a19706openalex-snapshot
Formal Languages and their Relation to Automata

What points at this work

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

inferred← citeshttps://doi.org/10.1007/3-540-07407-4_15openalex-snapshot
About the deterministic simulation of nondeterministic (log n)-tape bounded turing machines
inferred← citeshttps://doi.org/10.1007/3-540-08353-7_136openalex-snapshot
Properties of complexity classes a short survey
inferred← citeshttps://doi.org/10.1007/3-540-10843-2_40openalex-snapshot
Alternating multihead finite automata
inferred← citeshttps://doi.org/10.1007/3-540-10854-8_30openalex-snapshot
On the LBA problem
inferred← citeshttps://doi.org/10.1007/3-540-10856-4_98openalex-snapshot
Another hierarchy defined by multihead finite automata
inferred← citeshttps://doi.org/10.1007/3-540-45007-6_26openalex-snapshot
Computation with Absolutely No Space Overhead
inferred← citeshttps://doi.org/10.1007/3-540-45687-2_19openalex-snapshot
Two-Way Finite State Transducers with Nested Pebbles
inferred← citeshttps://doi.org/10.1007/3-540-48686-0_19openalex-snapshot
Circuits and Context-Free Languages
inferred← citeshttps://doi.org/10.1007/3-540-56939-1_106openalex-snapshot
Computing on structures
inferred← citeshttps://doi.org/10.1007/3-540-59042-0_107openalex-snapshot
On the structure of log-space probabilistic complexity classes
inferred← citeshttps://doi.org/10.1007/3-540-59175-3_103openalex-snapshot
Multihead two-way probabilistic finite automata
inferred← citeshttps://doi.org/10.1007/3-540-60249-6_66openalex-snapshot
Properties of probabilistic pushdown automata
inferred← citeshttps://doi.org/10.1007/978-3-030-10801-4_23openalex-snapshot
Multi-stranded String Assembling Systems
inferred← citeshttps://doi.org/10.1007/978-3-030-12797-8_8openalex-snapshot
APCol Systems with Verifier Agents
inferred← citeshttps://doi.org/10.1007/978-3-030-40608-0_12openalex-snapshot
Windable Heads and Recognizing NL with Constant Randomness
inferred← citeshttps://doi.org/10.1007/978-3-030-89543-3_14openalex-snapshot
Between SC and LOGDCFL: Families of Languages Accepted by Polynomial-Time Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata
inferred← citeshttps://doi.org/10.1007/978-3-031-66159-4_2openalex-snapshot
Polyregular Functions: Characterisations and Refutations
inferred← citeshttps://doi.org/10.1007/978-3-031-97274-4_13openalex-snapshot
String Assembling Systems: Origins and Directions
inferred← citeshttps://doi.org/10.1007/978-3-319-03898-8_28openalex-snapshot
Completeness Results for Parameterized Space Classes
inferred← citeshttps://doi.org/10.1007/978-3-319-08846-4_11openalex-snapshot
Unary Languages Recognized by Two-Way One-Counter Automata
inferred← citeshttps://doi.org/10.1007/978-3-319-08918-8_6openalex-snapshot
Unification and Logarithmic Space
inferred← citeshttps://doi.org/10.1007/978-3-642-28024-5_10openalex-snapshot
Finite dP Automata versus Multi-head Finite Automata
inferred← citeshttps://doi.org/10.1007/978-3-642-28332-1_9openalex-snapshot
Reversible Multi-head Finite Automata Characterize Reversible Logarithmic Space
inferred← citeshttps://doi.org/10.1007/978-3-642-30870-3_65openalex-snapshot
Finite State Verifiers with Constant Randomness
inferred← citeshttps://doi.org/10.1007/978-3-642-31653-1_2openalex-snapshot
P and dP Automata: Unconventional versus Classical Automata
inferred← citeshttps://doi.org/10.1007/978-3-642-33293-7_20openalex-snapshot
On the Space Complexity of Parameterized Problems
inferred← citeshttps://doi.org/10.1007/978-3-642-36315-3_2openalex-snapshot
One-Way Reversible Multi-head Finite Automata
inferred← citeshttps://doi.org/10.1007/978-3-662-46678-0_27openalex-snapshot
The Computational Contents of Ramified Corecurrence
inferred← citeshttps://doi.org/10.1007/bf00263746openalex-snapshot
Transformational methods and their application to complexity problems
inferred← citeshttps://doi.org/10.1007/bf00289080openalex-snapshot
A note on multihead automata and context-sensitive languages
inferred← citeshttps://doi.org/10.1007/bf01071364openalex-snapshot
Spatial complexity of recognition of context-free languages
inferred← citeshttps://doi.org/10.1007/bf01683260openalex-snapshot
Relativization of questions about log space computability
inferred← citeshttps://doi.org/10.1007/bf01683273openalex-snapshot
Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
inferred← citeshttps://doi.org/10.1007/bf01683283openalex-snapshot
Rudimentary relations and stack languages
inferred← citeshttps://doi.org/10.1007/bf01692057openalex-snapshot
On two-way weak counter machines
inferred← citeshttps://doi.org/10.1007/bf02679455openalex-snapshot
Multihead two-way probabilistic finite automata
inferred← citeshttps://doi.org/10.1007/bf03012191openalex-snapshot
Parallel communicating automata systems — A survey
inferred← citeshttps://doi.org/10.1007/bfb0029973openalex-snapshot
Multi-head finite automata: Data-independent versus data-dependent computations
inferred← citeshttps://doi.org/10.1007/bfb0036201openalex-snapshot
The equivalence of pebbles and sensing heads for finite automata
inferred← citeshttps://doi.org/10.1007/bfb0055779openalex-snapshot
The head hierarchy for oblivious finite automata with polynomial advice collapses
inferred← citeshttps://doi.org/10.1007/s00224-014-9547-7openalex-snapshot
The Complexity of Debate Checking
inferred← citeshttps://doi.org/10.1007/s00453-014-9944-yopenalex-snapshot
On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness
inferred← citeshttps://doi.org/10.1007/s10015-005-0373-5openalex-snapshot
Some properties of four-dimensional multicounter automata
inferred← citeshttps://doi.org/10.1007/s11047-022-09918-xopenalex-snapshot
Variants of string assembling systems
inferred← citeshttps://doi.org/10.1016/0020-0190(87)90172-4openalex-snapshot
Multiprocessor automata
inferred← citeshttps://doi.org/10.1016/0020-0255(79)90029-xopenalex-snapshot
Three-way two-dimensional multicounter automata
inferred← citeshttps://doi.org/10.1016/0022-0000(89)90019-6openalex-snapshot
Descriptive characterizations of computational complexity
inferred← citeshttps://doi.org/10.1016/0166-218x(89)90043-7openalex-snapshot
A new complete language for DSPACE(log n)
inferred← citeshttps://doi.org/10.1016/0304-3975(82)90087-1openalex-snapshot
Fooling a two way automation or one pushdown store is better than one counter for two way machines
inferred← citeshttps://doi.org/10.1016/0304-3975(86)90093-9openalex-snapshot
Hierarchies of one-way multihead automata languages
inferred← citeshttps://doi.org/10.1016/0304-3975(87)90071-5openalex-snapshot
Cyclic automata
inferred← citeshttps://doi.org/10.1016/0304-3975(88)90122-3openalex-snapshot
Alternating multihead finite automata
inferred← citeshttps://doi.org/10.1016/j.entcs.2011.09.025openalex-snapshot
Ramified Corecurrence and Logspace
inferred← citeshttps://doi.org/10.1016/j.ic.2005.05.005openalex-snapshot
Context-free languages can be accepted with absolutely no space overhead
inferred← citeshttps://doi.org/10.1016/j.ic.2014.01.018openalex-snapshot
Logarithmic space and permutations
inferred← citeshttps://doi.org/10.1016/j.ic.2021.104744openalex-snapshot
Constant-space, constant-randomness verifiers with arbitrarily small error
inferred← citeshttps://doi.org/10.1016/j.ipl.2012.04.009openalex-snapshot
On multi-head automata with restricted nondeterminism
inferred← citeshttps://doi.org/10.1016/j.irfa.2020.101631openalex-snapshot
Does economic policy uncertainty affect cross-border M&As? —— A data analysis based on Chinese multinational enterprises
inferred← citeshttps://doi.org/10.1016/j.jcss.2020.06.005openalex-snapshot
Tight hierarchy of data-independent multi-head automata
inferred← citeshttps://doi.org/10.1016/j.tcs.2004.04.013openalex-snapshot
On the descriptional power of heads, counters, and pebbles
inferred← citeshttps://doi.org/10.1016/j.tcs.2010.08.024openalex-snapshot
Complexity of multi-head finite automata: Origins and directions
inferred← citeshttps://doi.org/10.1016/j.tcs.2016.11.006openalex-snapshot
One-way reversible multi-head finite automata
inferred← citeshttps://doi.org/10.1016/s0019-9958(74)90473-2openalex-snapshot
Tally languages and complexity classes
inferred← citeshttps://doi.org/10.1016/s0019-9958(78)90570-3openalex-snapshot
Tape bounds for some subclasses of deterministic context-free languages
inferred← citeshttps://doi.org/10.1016/s0019-9958(79)90082-2openalex-snapshot
Equality languages and fixed point languages
inferred← citeshttps://doi.org/10.1016/s0020-0190(00)00159-9openalex-snapshot
Some undecidable problems for parallel communicating finite automata systems
inferred← citeshttps://doi.org/10.1016/s0020-0190(99)00129-5openalex-snapshot
Amplification of slight probabilistic advantage at absolutely no cost in space
inferred← citeshttps://doi.org/10.1016/s0022-0000(75)80014-6openalex-snapshot
On tape-bounded complexity classes and multihead finite automata
inferred← citeshttps://doi.org/10.1016/s0022-0000(77)80042-1openalex-snapshot
Relating refined space complexity classes
inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00237-7openalex-snapshot
Multi-head finite automata: data-independent versus data-dependent computations
inferred← citeshttps://doi.org/10.1016/s0304-3975(98)00059-0openalex-snapshot
Properties of probabilistic pushdown automata
inferred← citeshttps://doi.org/10.1017/s0960129519000112openalex-snapshot
Primitive recursion in the abstract
inferred← citeshttps://doi.org/10.1051/ita/1977110301811openalex-snapshot
Some remarks on multihead automata
inferred← citeshttps://doi.org/10.1051/ita/2012020openalex-snapshot
String Assembling Systems
inferred← citeshttps://doi.org/10.1051/ita/2013046openalex-snapshot
Systems of parallel communicating restarting automata
inferred← citeshttps://doi.org/10.1051/ita/2013048openalex-snapshot
Bidirectional string assembling systems
inferred← citeshttps://doi.org/10.1051/ita/2018009openalex-snapshot
Diving into the queue
inferred← citeshttps://doi.org/10.1051/ita:2007014openalex-snapshot
Returning and non-returning parallel communicating finite automata are equivalent
inferred← citeshttps://doi.org/10.1080/00207167408803092openalex-snapshot
Some results concerning automata on two-dimensional tapes
inferred← citeshttps://doi.org/10.1080/23799927.2023.2166872openalex-snapshot
Between SC and LOGDCFL: families of languages accepted by logarithmic-space deterministic auxiliary depth-k storage automata
inferred← citeshttps://doi.org/10.1109/istcs.1995.377036openalex-snapshot
Automata with sensing heads
inferred← citeshttps://doi.org/10.1109/swat.1973.20openalex-snapshot
On tape-bounded complexity classes and multi-head finite automata
inferred← citeshttps://doi.org/10.1109/swat.1974.29openalex-snapshot
Two way deterministic pushdown automaton languages and some open problems in the theory of computation
inferred← citeshttps://doi.org/10.1137/s0097539796298339openalex-snapshot
On the Structure of Logspace Probabilistic Complexity Classes
inferred← citeshttps://doi.org/10.1142/s0129054100000338openalex-snapshot
PARALLEL COMMUNICATING PUSHDOWN AUTOMATA SYSTEMS
inferred← citeshttps://doi.org/10.1142/s0129054102001424openalex-snapshot
PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES
inferred← citeshttps://doi.org/10.1145/211542.606544openalex-snapshot
SIGACT News Complexity Theory Column 10
inferred← citeshttps://doi.org/10.1145/322077.322083openalex-snapshot
On the Tape Complexity of Deterministic Context-Free Languages
inferred← citeshttps://doi.org/10.1145/800076.802471openalex-snapshot
Fooling a two-way automaton or one pushdown store is better than one counter for two way machines (Preliminary Version)
inferred← citeshttps://doi.org/10.1145/800113.803642openalex-snapshot
On deterministic context-free languages, multihead automata, and the power of an auxiliary pushdown store
inferred← citeshttps://doi.org/10.1145/977091.977113openalex-snapshot
Watson-Crick automata and PCFAS with two components
inferred← citeshttps://doi.org/10.1184/r1/6607520openalex-snapshot
Monotonic use of space and computational complexity over abstract structures
inferred← citeshttps://doi.org/10.14279/depositonce-617openalex-snapshot
On structural similarities of finite automata and Turing machine enumerability classes
inferred← citeshttps://doi.org/10.2168/lmcs-10(3:6)2014openalex-snapshot
Finite state verifiers with constant randomness
inferred← citeshttps://doi.org/10.2168/lmcs-3(2:3)2007openalex-snapshot
Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure
inferred← citeshttps://doi.org/10.23638/lmcs-14(3:6)2018openalex-snapshot
Unification and Logarithmic Space
inferred← citeshttps://doi.org/10.3233/fi-2015-1149openalex-snapshot
Asynchronous Systems of Parallel Communicating Finite Automata
inferred← citeshttps://doi.org/10.4204/eptcs.1.9openalex-snapshot
Multi-Head Finite Automata: Characterizations, Concepts and Open Problems
inferred← citeshttps://doi.org/10.4230/oasics.tannen.2openalex-snapshot
Traversal-Invariant Characterizations of Logarithmic Space
inferred← citeshttps://doi.org/10.48550/arxiv.1211.7346openalex-snapshot
Checking generalized debates with small space and randomness
inferred← citeshttps://doi.org/10.48550/arxiv.1308.2892openalex-snapshot
Completeness Results for Parameterized Space Classes
inferred← citeshttps://doi.org/10.48550/arxiv.1311.0849openalex-snapshot
Unary languages recognized by two-way one-counter automata
inferred← citeshttps://doi.org/10.48550/arxiv.1802.03115openalex-snapshot
Implicit complexity via structure transformation
inferred← citeshttps://doi.org/10.5281/zenodo.806771openalex-snapshot
On The Resolution Semiring
inferred← citeshttps://doi.org/10.70675/3b6c23dezc274z4bf0zbb66z44b63eeb61e7openalex-snapshot
On the Resolution Semiring
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.