On the public citation graph

Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations

https://doi.org/10.1007/bfb0023453
0 signed · 51 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-10856-4_72openalex-snapshot
Probabilistic two-way machines
inferredcites →https://doi.org/10.1007/bf02090764openalex-snapshot
Classes of bounded nondeterminism
inferredcites →https://doi.org/10.1108/ir.1999.04926fae.001openalex-snapshot
Lecture Notes in Computer Science 1205
inferredcites →https://doi.org/10.1109/swat.1971.11openalex-snapshot
Economy of description by automata, grammars, and formal systems
inferredcites →https://doi.org/10.1145/237814.238003openalex-snapshot
Nondeterministic communication with a limited number of advice bits
inferredcites →https://doi.org/10.1145/800061.808742openalex-snapshot
On notions of information transfer in VLSI circuits
inferredcites →https://doi.org/10.1145/800070.802208openalex-snapshot
Las Vegas Is better than Determinism in VLSI and Distributed Computing
inferredcites →https://doi.org/10.1145/800076.802483openalex-snapshot
The entropic limitations on VLSI computations(Extended Abstract)
inferredcites →https://doi.org/10.2307/2584070openalex-snapshot
Introduction to the Theory of Complexity.

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.3069openalex-snapshot
Communication Complexity Method for Measuring Nondeterminism in Finite Automata
inferred← citeshttps://doi.org/10.1007/3-540-45022-x_17openalex-snapshot
Measures of Nondeterminism in Finite Automata
inferred← citeshttps://doi.org/10.1007/3-540-45061-0_7openalex-snapshot
Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes
inferred← citeshttps://doi.org/10.1007/3-540-46011-x_22openalex-snapshot
On the Power of Randomized Pushdown Automata
inferred← citeshttps://doi.org/10.1007/3-540-46541-3_12openalex-snapshot
Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs
inferred← citeshttps://doi.org/10.1007/3-540-48523-6_40openalex-snapshot
On the Power of Las Vegas II. Two-Way Finite Automata
inferred← citeshttps://doi.org/10.1007/3-540-49116-3_46openalex-snapshot
On the Size of Randomized OBDDs and Read-Once Branching Programs for k-Stable Functions
inferred← citeshttps://doi.org/10.1007/3-540-63890-3_27openalex-snapshot
On the size of probabilistic formulae
inferred← citeshttps://doi.org/10.1007/978-3-030-20981-0_6openalex-snapshot
Iterative Arrays with Self-verifying Communication Cell
inferred← citeshttps://doi.org/10.1007/978-3-319-09704-6_12openalex-snapshot
Classical Automata on Promise Problems
inferred← citeshttps://doi.org/10.1007/978-3-319-20297-6_16openalex-snapshot
Operations on Self-Verifying Finite Automata
inferred← citeshttps://doi.org/10.1007/978-3-319-41114-9_3openalex-snapshot
Self-Verifying Finite Automata and Descriptional Complexity
inferred← citeshttps://doi.org/10.1007/978-3-319-94631-3_15openalex-snapshot
Error-Free Affine, Unitary, and Probabilistic OBDDs
inferred← citeshttps://doi.org/10.1007/978-3-319-98355-4_9openalex-snapshot
Classical and Quantum Computations with Restricted Memory
inferred← citeshttps://doi.org/10.1007/978-3-319-98654-8_33openalex-snapshot
Computational Complexity of Decision Problems on Self-verifying Finite Automata
inferred← citeshttps://doi.org/10.1007/978-3-319-99813-8_31openalex-snapshot
Self-verifying Cellular Automata
inferred← citeshttps://doi.org/10.1007/978-3-540-45077-1_16openalex-snapshot
One-Way Communication Complexity of Symmetric Boolean Functions
inferred← citeshttps://doi.org/10.1007/978-3-642-00982-2_39openalex-snapshot
Converting Self-verifying Automata into Deterministic Automata
inferred← citeshttps://doi.org/10.1007/978-3-642-12200-2_19openalex-snapshot
Pairs of Complementary Unary Languages with “Balanced” Nondeterministic Automata
inferred← citeshttps://doi.org/10.1007/978-3-642-28332-1_23openalex-snapshot
Two-Way Automata Making Choices Only at the Endmarkers
inferred← citeshttps://doi.org/10.1007/bfb0029950openalex-snapshot
Communication complexity and sequential computation
inferred← citeshttps://doi.org/10.1007/s00224-007-9066-xopenalex-snapshot
Probabilistic Length-Reducing Two-Pushdown Automata
inferred← citeshttps://doi.org/10.1007/s00453-010-9479-9openalex-snapshot
Pairs of Complementary Unary Languages with “Balanced” Nondeterministic Automata
inferred← citeshttps://doi.org/10.1007/s11047-020-09812-4openalex-snapshot
Iterative arrays with self-verifying communication cell
inferred← citeshttps://doi.org/10.1016/j.ic.2010.11.017openalex-snapshot
Optimal simulation of self-verifying automata by deterministic automata
inferred← citeshttps://doi.org/10.1016/j.ic.2014.08.009openalex-snapshot
Two-way automata making choices only at the endmarkers
inferred← citeshttps://doi.org/10.1016/j.jcss.2003.11.007openalex-snapshot
On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
inferred← citeshttps://doi.org/10.1016/j.jcss.2011.06.004openalex-snapshot
Size complexity of rotating and sweeping automata
inferred← citeshttps://doi.org/10.1016/j.tcs.2004.09.015openalex-snapshot
On the power of randomized multicounter machines
inferred← citeshttps://doi.org/10.1016/j.tcs.2009.03.020openalex-snapshot
On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA’s
inferred← citeshttps://doi.org/10.1016/s0304-3975(00)00155-9openalex-snapshot
On the power of Las Vegas II: Two-way finite automata
inferred← citeshttps://doi.org/10.1051/ita:2003007openalex-snapshot
Lower Bounds for Las Vegas Automata by Information Theory
inferred← citeshttps://doi.org/10.1109/ccc.2000.856752openalex-snapshot
A separation of determinism, Las Vegas and nondeterminism for picture recognition
inferred← citeshttps://doi.org/10.1109/ccc.2004.1313854openalex-snapshot
Limitations of quantum advice and one-way communication
inferred← citeshttps://doi.org/10.1109/ccc.2004.16openalex-snapshot
Limitations of quantum advice and one-way communication
inferred← citeshttps://doi.org/10.1109/csss.2012.474openalex-snapshot
Comparison of Two-Way Two-Dimensional Finite Automata and Three-Way Two-Dimensional Finite Automata
inferred← citeshttps://doi.org/10.1142/s0129054121500246openalex-snapshot
Error-Free Affine, Unitary, and Probabilistic OBDDs
inferred← citeshttps://doi.org/10.1145/335305.335396openalex-snapshot
On quantum and probabilistic communication
inferred← citeshttps://doi.org/10.25596/jalc-2002-419openalex-snapshot
3-Party Message Complexity is Better than 2-Party Ones for Proving Lower Bounds on the Size of Minimal Nondeterministic Finite Automata
inferred← citeshttps://doi.org/10.25596/jalc-2002-519openalex-snapshot
Descriptional Complexity of Finite Automata: Concepts and Open Problems
inferred← citeshttps://doi.org/10.46298/dmtcs.2138openalex-snapshot
Classical Automata on Promise Problems
inferred← citeshttps://doi.org/10.48550/arxiv.quant-ph/0412143openalex-snapshot
Limits on Efficient Computation in the Physical World
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.