On the public citation graph

The complexity of computing maximal word functions

https://doi.org/10.1007/bf01275489
0 signed · 54 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-08138-0_11openalex-snapshot
On one-way Auxiliary pushdown automata
inferredcites →https://doi.org/10.1007/3-540-52921-7_71openalex-snapshot
Algorithms from complexity theory: Polynomial-time operations for complex sets
inferredcites →https://doi.org/10.1007/3-540-55719-9_65openalex-snapshot
On growing context-sensitive languages
inferredcites →https://doi.org/10.1007/978-3-642-79235-9openalex-snapshot
Structural Complexity I
inferredcites →https://doi.org/10.1007/bf00289308openalex-snapshot
?-productions in context-free grammars
inferredcites →https://doi.org/10.1007/bf01268143openalex-snapshot
A note on logspace optimization
inferredcites →https://doi.org/10.1007/bf01744431openalex-snapshot
Parity, circuits, and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1007/bf02090763openalex-snapshot
The complexity of ranking simple languages
inferredcites →https://doi.org/10.1016/0020-0190(91)90015-aopenalex-snapshot
Rudimentary reductions revisited
inferredcites →https://doi.org/10.1016/0022-0000(81)90038-6openalex-snapshot
On uniform circuit complexity
inferredcites →https://doi.org/10.1016/0022-0000(88)90039-6openalex-snapshot
The complexity of optimization problems
inferredcites →https://doi.org/10.1016/0022-0000(90)90022-dopenalex-snapshot
On uniformity within NC1
inferredcites →https://doi.org/10.1016/0022-0000(90)90038-mopenalex-snapshot
On the complexity of ranking
inferredcites →https://doi.org/10.1016/0022-0000(91)90020-6openalex-snapshot
Properties that characterize LOGCFL
inferredcites →https://doi.org/10.1016/0304-3975(86)90174-xopenalex-snapshot
Random generation of combinatorial structures from a uniform distribution
inferredcites →https://doi.org/10.1016/0304-3975(91)90023-uopenalex-snapshot
The complexity of computing the number of strings of given length in context-free languages
inferredcites →https://doi.org/10.1016/0304-3975(91)90144-qopenalex-snapshot
Ranking and formal power series
inferredcites →https://doi.org/10.1016/0304-3975(93)90252-oopenalex-snapshot
A very hard log-space counting class
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/0890-5401(91)90010-yopenalex-snapshot
Two dynamic programming algorithms for which interpreted pebbling helps
inferredcites →https://doi.org/10.1016/b978-0-444-88071-0.50022-9openalex-snapshot
Parallel Algorithms for Shared-Memory Machines
inferredcites →https://doi.org/10.1016/s0019-9958(85)80041-3openalex-snapshot
A taxonomy of problems with fast parallel algorithms
inferredcites →https://doi.org/10.1109/sct.1988.5280openalex-snapshot
The complexity of ranking
inferredcites →https://doi.org/10.1137/0208032openalex-snapshot
The Complexity of Enumeration and Reliability Problems
inferredcites →https://doi.org/10.1137/0213027openalex-snapshot
Simulation of Parallel Random Access Machines by Circuits
inferredcites →https://doi.org/10.1137/0213028openalex-snapshot
Constant Depth Reducibility
inferredcites →https://doi.org/10.1137/0217044openalex-snapshot
Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
inferredcites →https://doi.org/10.1137/0217075openalex-snapshot
P-Printable Sets
inferredcites →https://doi.org/10.1137/0218038openalex-snapshot
Two Applications of Inductive Counting for Complementation Problems
inferredcites →https://doi.org/10.1137/0219019openalex-snapshot
On the Efficient Generation of Language Instances
inferredcites →https://doi.org/10.1137/0220034openalex-snapshot
Compression and Ranking
inferredcites →https://doi.org/10.1137/0221046openalex-snapshot
An Optimal Parallel Algorithm for Formula Evaluation
inferredcites →https://doi.org/10.1142/s0129054191000121openalex-snapshot
EFFICIENT DETECTORS AND CONSTRUCTORS FOR SIMPLE LANGUAGES
inferredcites →https://doi.org/10.1145/167088.167226openalex-snapshot
Depth reduction for noncommutative arithmetic circuits
inferredcites →https://doi.org/10.1145/2422.322412openalex-snapshot
Bounding Fan-out in Logical Networks
inferredcites →https://doi.org/10.1145/321623.321625openalex-snapshot
Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
inferredcites →https://doi.org/10.1145/76359.76370openalex-snapshot
P-uniform circuit complexity
inferredcites →https://doi.org/10.5555/11534.11537openalex-snapshot
Random generation of combinatorial structures from a uniform

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.1997.2621openalex-snapshot
A Quasi-polynomial-time Algorithm for Sampling Words from a Context-Free Language
inferred← citeshttps://doi.org/10.1006/inco.2000.2914openalex-snapshot
How Hard Is Computing the Edit Distance?
inferred← citeshttps://doi.org/10.1007/3-540-44693-1_27openalex-snapshot
On the Circuit Complexity of Random Generation Problems for Regular and Context-Free Languages
inferred← citeshttps://doi.org/10.1007/3-540-46541-3_47openalex-snapshot
Random Generation and Approximate Counting of Ambiguously Described Combinatorial Structures
inferred← citeshttps://doi.org/10.1007/3-540-58338-6_71openalex-snapshot
On languages accepted with simultaneous complexity bounds and their ranking problem
inferred← citeshttps://doi.org/10.1007/3-540-60249-6_70openalex-snapshot
How hard is to compute the edit distance
inferred← citeshttps://doi.org/10.1007/978-1-4612-1872-2_7openalex-snapshot
The Complexity of Obtaining Solutions for Problems in NP and NL
inferred← citeshttps://doi.org/10.1007/978-3-319-03780-6_28openalex-snapshot
Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems
inferred← citeshttps://doi.org/10.1007/978-3-540-24587-2_11openalex-snapshot
The Intractability of Computing the Hamming Distance
inferred← citeshttps://doi.org/10.1007/bf01268143openalex-snapshot
A note on logspace optimization
inferred← citeshttps://doi.org/10.1007/s00037-005-0198-6openalex-snapshot
Compression of Samplable Sources
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.02.002openalex-snapshot
The intractability of computing the Hamming distance
inferred← citeshttps://doi.org/10.1016/s0304-3975(97)00227-2openalex-snapshot
Non-commutative arithmetic circuits: depth reduction and size lower bounds
inferred← citeshttps://doi.org/10.1051/ita:2001128openalex-snapshot
Random Generation for Finitely Ambiguous Context-free Languages
inferred← citeshttps://doi.org/10.1051/ita:2006010openalex-snapshot
String distances and intrusion detection: Bridging the gap between formal languages and computer security
inferred← citeshttps://doi.org/10.1109/ccc.2004.1313766openalex-snapshot
Compression of samplable sources
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.