On the public citation graph

Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds

https://doi.org/10.1006/jcss.2002.1855

0 signed · 66 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.1006/inco.1997.2682openalex-snapshot

Bridging across the log(n) Space Frontier

inferredcites →https://doi.org/10.1006/jcss.1996.0046openalex-snapshot

Automaticity I: Properties of a Measure of Descriptional Complexity

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-54458-5_73openalex-snapshot

Regularity of one-letter languages acceptable by 2-way finite probabilistic automata

inferredcites →https://doi.org/10.1007/3-540-58355-6openalex-snapshot

Turing Machines with Sublogarithmic Space

inferredcites →https://doi.org/10.1007/3-540-60246-1_137openalex-snapshot

Strong optimal lower bounds for Turing machines that accept nonregular languages

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

Space complexity of alternating Turing machines

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/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(86)90142-8openalex-snapshot

Finite automata and unary languages

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

Introduction to automata theory, languages and computation

inferredcites →https://doi.org/10.1109/focs.1965.11openalex-snapshot

Hierarchies of memory limited computations

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

Economy of description by automata, grammars, and formal systems

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

Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space

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

Sublogarithmic Bounds on Space and Reversals

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

Optimal Simulations between Unary Automata

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

UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION

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

Two Families of Languages Related to ALGOL

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

On Context-Free Languages

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

Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines

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

Some Results on Tape-Bounded Turing Machines

inferredcites →https://doi.org/10.2307/2371684openalex-snapshot

On a Problem of Partitions

inferredcites →https://doi.org/10.3233/fi-1986-9303openalex-snapshot

Almost Context-Free Languages

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-030-23247-4_20openalex-snapshot

Pushdown Automata and Constant Height: Decidability and Bounds

inferred← citeshttps://doi.org/10.1007/978-3-031-40247-0_19openalex-snapshot

Two-Way Machines and de Bruijn Words

inferred← citeshttps://doi.org/10.1007/978-3-031-71112-1_21openalex-snapshot

Push Complexity: Optimal Bounds and Unary Inputs

inferred← citeshttps://doi.org/10.1007/978-3-319-08019-2_26openalex-snapshot

Complexity of Operation Problems

inferred← citeshttps://doi.org/10.1007/978-3-319-08846-4_3openalex-snapshot

Investigations on Automata and Languages over a Unary Alphabet

inferred← citeshttps://doi.org/10.1007/978-3-319-09704-6_31openalex-snapshot

Non-recursive Trade-offs between Two-Dimensional Automata and Grammars

inferred← citeshttps://doi.org/10.1007/978-3-319-19225-3_13openalex-snapshot

On Simulation Cost of Unary Limited Automata

inferred← citeshttps://doi.org/10.1007/978-3-319-22360-5_21openalex-snapshot

(Un)decidability of the Emptiness Problem for Multi-dimensional Context-Free Grammars

inferred← citeshttps://doi.org/10.1007/978-3-319-62809-7_23openalex-snapshot

Limited Automata and Unary Languages

inferred← citeshttps://doi.org/10.1007/978-3-319-94812-6_16openalex-snapshot

Non-self-embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata

inferred← citeshttps://doi.org/10.1007/978-3-540-70844-5_24openalex-snapshot

Deterministic Pushdown Automata and Unary Languages

inferred← citeshttps://doi.org/10.1007/978-3-540-73208-2_30openalex-snapshot

Descriptional Complexity of Bounded Context-Free Languages

inferred← citeshttps://doi.org/10.1007/978-3-642-15349-5_1openalex-snapshot

Descriptional Complexity of (Un)ambiguous Finite State Machines and Pushdown Automata

inferred← citeshttps://doi.org/10.1007/978-3-642-22600-7_20openalex-snapshot

Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals

inferred← citeshttps://doi.org/10.1007/978-3-642-27660-6_30openalex-snapshot

Parikh’s Theorem and Descriptional Complexity

inferred← citeshttps://doi.org/10.1007/978-3-642-31653-1_26openalex-snapshot

Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata

inferred← citeshttps://doi.org/10.1007/978-3-642-39310-5_15openalex-snapshot

Size of Unary One-Way Multi-head Finite Automata

inferred← citeshttps://doi.org/10.1007/s00236-022-00434-0openalex-snapshot

Pushdown automata and constant height: decidability and bounds

inferred← citeshttps://doi.org/10.1016/j.ic.2013.03.008openalex-snapshot

Descriptional complexity of bounded context-free languages

inferred← citeshttps://doi.org/10.1016/j.ic.2013.06.003openalex-snapshot

Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata

inferred← citeshttps://doi.org/10.1016/j.ic.2015.08.005openalex-snapshot

Deciding determinism of unary languages

inferred← citeshttps://doi.org/10.1016/j.ic.2017.09.005openalex-snapshot

Descriptional complexity of limited automata

inferred← citeshttps://doi.org/10.1016/j.ic.2019.01.002openalex-snapshot

Limited automata and unary languages

inferred← citeshttps://doi.org/10.1016/j.is.2024.102475openalex-snapshot

Explaining results of path queries on graphs: Single-path results for context-free path queries

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

Descriptional complexity of two-way pushdown automata with restricted head reversals

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

Non-recursive trade-offs between two-dimensional automata and grammars

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

Undecidability of the emptiness problem for context-free picture languages

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

Nondeterministic complexity in subclasses of convex languages

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

Push complexity: Optimal bounds and decidability

inferred← citeshttps://doi.org/10.1109/lics.2010.21openalex-snapshot

Parikh Images of Grammars: Complexity and Applications

inferred← citeshttps://doi.org/10.1109/powercon.2018.8601619openalex-snapshot

Computational Complexity of Algorithms for Optimization of Multi-Hybrid Renewable Energy Systems

inferred← citeshttps://doi.org/10.1142/s0129054109006784openalex-snapshot

DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES

inferred← citeshttps://doi.org/10.1142/s0129054114400139openalex-snapshot

SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA

inferred← citeshttps://doi.org/10.1142/s012905411540002xopenalex-snapshot

Investigations on Automata and Languages Over a Unary Alphabet

inferred← citeshttps://doi.org/10.1142/s0129054120420071openalex-snapshot

Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata

inferred← citeshttps://doi.org/10.20904/271025openalex-snapshot

Ordered Pure Multi-Pushdown Automata

inferred← citeshttps://doi.org/10.3233/fi-2015-1148openalex-snapshot

Limited Automata and Context-Free Languages

inferred← citeshttps://doi.org/10.3233/fi-2015-1198openalex-snapshot

Semilinear Sets and Counter Machines: a Brief Survey

inferred← citeshttps://doi.org/10.4204/eptcs.407.10openalex-snapshot

Complexity of Unary Exclusive Nondeterministic Finite Automata

inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2014.339openalex-snapshot

Notes on Counting with Finite Machines

inferred← citeshttps://doi.org/10.48550/arxiv.0905.1045openalex-snapshot

Descriptional complexity of bounded context-free languages

inferred← citeshttps://doi.org/10.48550/arxiv.0905.1248openalex-snapshot

Deterministic pushdown automata and unary languages

inferred← citeshttps://doi.org/10.48550/arxiv.1002.1464openalex-snapshot

Parikh Images of Regular Languages: Complexity and Applications

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.