On the public citation graph
Subcubic certificates for CFL reachability
0 signed · 76 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.1007/3-540-09526-8_5openalex-snapshot
Fast probabilistic algorithms
inferredcites →https://doi.org/10.1007/3-540-63141-0_10openalex-snapshot
Reachability analysis of pushdown automata: Application to model-checking
inferredcites →https://doi.org/10.1007/978-3-030-13435-8_1openalex-snapshot
Modern Aspects of Complexity Within Formal Languages
inferredcites →https://doi.org/10.1007/978-3-030-48516-0_6openalex-snapshot
On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
inferredcites →https://doi.org/10.1007/978-3-030-61133-0_7openalex-snapshot
Explaining Results of Path Queries on Graphs
inferredcites →https://doi.org/10.1007/978-3-319-04298-5_33openalex-snapshot
Deterministic Verification of Integer Matrix Multiplication in Quadratic Time
inferredcites →https://doi.org/10.1007/978-3-319-98654-8_23openalex-snapshot
Intersection Non-emptiness and Hardness Within Polynomial Time
inferredcites →https://doi.org/10.1007/978-3-662-43951-7_30openalex-snapshot
Hardness Results for Intersection Non-Emptiness
inferredcites →https://doi.org/10.1007/978-3-662-47666-6_33openalex-snapshot
On the Complexity of Intersecting Regular, Context-Free, and Tree Languages
inferredcites →https://doi.org/10.1007/bf01683273openalex-snapshot
Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
inferredcites →https://doi.org/10.1016/0020-0190(81)90045-4openalex-snapshot
A hardest language recognized by two-way nondeterministic pushdown automata
inferredcites →https://doi.org/10.1016/0020-0190(93)90224-wopenalex-snapshot
A probabilistic algorithm for verifying matrix products using O(n2) time and log2n + O(1) random bits
inferredcites →https://doi.org/10.1016/0095-8956(91)90068-uopenalex-snapshot
Quickly excluding a forest
inferredcites →https://doi.org/10.1016/0304-3975(82)90110-4openalex-snapshot
A pushdown automation or a context-free grammar—which is more economical?
inferredcites →https://doi.org/10.1016/0304-3975(92)90269-lopenalex-snapshot
Rational indexes of generators of the cone of context-free languages
inferredcites →https://doi.org/10.1016/j.ipl.2017.02.003openalex-snapshot
Pushdown reachability with constant treewidth
inferredcites →https://doi.org/10.1016/j.ipl.2019.105841openalex-snapshot
Proving that prBPP = prP is as hard as proving that “almost NP” is not contained in P/poly
inferredcites →https://doi.org/10.1016/j.ipl.2020.105993openalex-snapshot
Lengths of words accepted by nondeterministic finite automata
inferredcites →https://doi.org/10.1016/s0019-9958(67)90369-5openalex-snapshot
Two-way pushdown automata
inferredcites →https://doi.org/10.1016/s0019-9958(68)91087-5openalex-snapshot
Time and tape complexity of pushdown automaton languages
inferredcites →https://doi.org/10.1016/s0019-9958(82)90401-6openalex-snapshot
On the security of ping-pong protocols
inferredcites →https://doi.org/10.1016/s0019-9958(85)80024-3openalex-snapshot
Fast recognition of pushdown automaton and context-free languages
inferredcites →https://doi.org/10.1016/s0020-0190(00)00055-7openalex-snapshot
An efficient automata approach to some problems on context-free grammars
inferredcites →https://doi.org/10.1016/s0022-0000(75)80046-8openalex-snapshot
General context-free recognition in less than cubic time
inferredcites →https://doi.org/10.1016/s0304-3975(00)00049-9openalex-snapshot
Interconvertibility of a class of set constraints and context-free-language reachability
inferredcites →https://doi.org/10.1016/s0747-7171(08)80013-2openalex-snapshot
Matrix multiplication via arithmetic progressions
inferredcites →https://doi.org/10.1016/s1571-0661(05)80426-8openalex-snapshot
A Direct Symbolic Approach to Model Checking Pushdown Systems (extended abstract)
inferredcites →https://doi.org/10.1109/focs.1965.11openalex-snapshot
Hierarchies of memory limited computations
inferredcites →https://doi.org/10.1109/focs.2015.16openalex-snapshot
If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
inferredcites →https://doi.org/10.1109/focs.2016.56openalex-snapshot
Which Regular Expression Patterns Are Hard to Match?
inferredcites →https://doi.org/10.1109/focs.2017.36openalex-snapshot
A Dichotomy for Regular Expression Membership Testing
inferredcites →https://doi.org/10.1109/lics.1997.614960openalex-snapshot
On the cubic bottleneck in subtyping and flow analysis
inferredcites →https://doi.org/10.1111/j.1467-8640.1994.tb00011.xopenalex-snapshot
RECOGNITION CAN BE HARDER THAN PARSING
inferredcites →https://doi.org/10.1134/s003294601104003xopenalex-snapshot
On regular realizability problems
inferredcites →https://doi.org/10.1134/s0032946015040043openalex-snapshot
On regular realizability problems for context-free languages
inferredcites →https://doi.org/10.1137/0210020openalex-snapshot
The Rational Index: A Complexity Measure for Languages
inferredcites →https://doi.org/10.1142/9789813272880_0188openalex-snapshot
ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
inferredcites →https://doi.org/10.1145/1075382.1075387openalex-snapshot
Analysis of recursive state machines
inferredcites →https://doi.org/10.1145/1328438.1328460openalex-snapshot
Subcubic algorithms for recursive state machines
inferredcites →https://doi.org/10.1145/199448.199462openalex-snapshot
Precise interprocedural dataflow analysis via graph reachability
inferredcites →https://doi.org/10.1145/2213977.2214056openalex-snapshot
Multiplying matrices faster than coppersmith-winograd
inferredcites →https://doi.org/10.1145/22145.22192openalex-snapshot
Trading group theory for randomness
inferredcites →https://doi.org/10.1145/2840728.2840746openalex-snapshot
Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
inferredcites →https://doi.org/10.1145/298514.298576openalex-snapshot
Graph-theoretic methods in database theory
inferredcites →https://doi.org/10.1145/3158118openalex-snapshot
Optimal Dyck reachability for data-dependence and alias analysis
inferredcites →https://doi.org/10.1145/3186893openalex-snapshot
Subcubic Equivalences Between Path, Matrix, and Triangle Problems
inferredcites →https://doi.org/10.1145/3434315openalex-snapshot
The fine-grained and parallel complexity of andersen’s pointer analysis
inferredcites →https://doi.org/10.1145/505241.505242openalex-snapshot
Fast context-free grammar parsing requires fast boolean matrix multiplication
inferredcites →https://doi.org/10.13140/rg.2.2.12022.09280openalex-snapshot
Efficient Exact Paths For Dyck and semi-Dyck Labeled Path Reachability
inferredcites →https://doi.org/10.1515/gcc-2012-0016openalex-snapshot
Algorithmics on SLP-compressed strings: A survey
inferredcites →https://doi.org/10.15479/at:ist-2017-870-v1-1openalex-snapshot
Optimal Dyck Reachability for Data-Dependence and Alias Analysis
inferredcites →https://doi.org/10.3390/a10010024openalex-snapshot
Problems on Finite Automata and the Exponential Time Hypothesis
inferredcites →https://doi.org/10.4204/eptcs.151.1openalex-snapshot
Saturation algorithms for model-checking pushdown systems
inferredcites →https://doi.org/10.4230/lipics.esa.2018.56openalex-snapshot
On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress
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-031-57231-9openalex-snapshot
Foundations of Software Science and Computation Structures
inferred← citeshttps://doi.org/10.1007/978-3-031-57231-9_9openalex-snapshot
Reachability in Fixed VASS: Expressiveness and Lower Bounds
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00059openalex-snapshot
A tight (non-combinatorial) conditional lower bound for Klee’s Measure Problem in 3D
inferred← citeshttps://doi.org/10.1109/lics56636.2023.10175714openalex-snapshot
On Certificates, Expected Runtimes, and Termination in Probabilistic Pushdown Automata
inferred← citeshttps://doi.org/10.1109/lics65433.2025.00053openalex-snapshot
Pushdown Model Checking above the Cubic Bottleneck
inferred← citeshttps://doi.org/10.1134/s0032946024030050openalex-snapshot
On Universality of Regular Realizability Problems
inferred← citeshttps://doi.org/10.1134/s0037446626050198openalex-snapshot
Computable Isomorphisms of Relative Regular Boolean Algebras
inferred← citeshttps://doi.org/10.1142/s0129054124420073openalex-snapshot
Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems
inferred← citeshttps://doi.org/10.1145/3571252openalex-snapshot
The Fine-Grained Complexity of CFL Reachability
inferred← citeshttps://doi.org/10.1145/3632743openalex-snapshot
Octopus : Scaling Value-Flow Analysis via Parallel Collection of Realizable Path Conditions
inferred← citeshttps://doi.org/10.1145/3632884openalex-snapshot
On-the-Fly Static Analysis via Dynamic Bidirected Dyck Reachability
inferred← citeshttps://doi.org/10.1145/3644389openalex-snapshot
Dynamic Transitive Closure-based Static Analysis through the Lens of Quantum Search
inferred← citeshttps://doi.org/10.1145/3661814.3662134openalex-snapshot
Slice closures of indexed languages and word equations with counting constraints
inferred← citeshttps://doi.org/10.1145/3704854openalex-snapshot
Program Analysis via Multiple Context Free Language Reachability
inferred← citeshttps://doi.org/10.1145/3721145.3725762openalex-snapshot
GraCFL: A Holistically Designed Vertex-Centric Graph System for CFL Reachability
inferred← citeshttps://doi.org/10.31857/s0555292324030069openalex-snapshot
Regular Realizability Problems for Descriptions of Finite Relations
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.