On the public citation graph

Alternating Pushdown and Stack Automata

0 signed · 121 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/bf01786980openalex-snapshot

(Semi)alternating stack automata

inferredcites →https://doi.org/10.1016/0022-0000(79)90046-1openalex-snapshot

Propositional dynamic logic of regular programs

inferredcites →https://doi.org/10.1016/0022-0000(80)90027-6openalex-snapshot

Complexity results for classes of quantificational formulas

inferredcites →https://doi.org/10.1016/0022-0000(80)90033-1openalex-snapshot

The complexity of problems in systems of communicating sequential processes

inferredcites →https://doi.org/10.1016/0022-0000(80)90036-7openalex-snapshot

Tree-size bounded alternation

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/0097-3165(81)90016-9openalex-snapshot

Computing a perfect strategy for n × n chess requires time exponential in n

inferredcites →https://doi.org/10.1016/0304-3975(80)90037-7openalex-snapshot

The complexity of logical theories

inferredcites →https://doi.org/10.1016/0304-3975(80)90048-1openalex-snapshot

Complexity of Boolean algebras

inferredcites →https://doi.org/10.1016/s0019-9958(67)90369-5openalex-snapshot

Two-way pushdown automata

inferredcites →https://doi.org/10.1016/s0022-0000(67)80013-8openalex-snapshot

Nonerasing stack automata

inferredcites →https://doi.org/10.1016/s0022-0000(71)80029-6openalex-snapshot

Characterizations of some tape and time complexity classes of turing machines in terms of multihead and auxiliary stack automata

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

Provably Difficult Combinatorial Games

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

Path Systems: Constructions, Solutions and Applications

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

Stack automata and compiling

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/322234.322243openalex-snapshot

Alternation

inferredcites →https://doi.org/10.1147/rd.32.0198openalex-snapshot

The Reduction of Two-Way Automata to One-Way 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-36285-1_5openalex-snapshot

Typechecking Top-Down Uniform Unranked Tree Transducers

inferred← citeshttps://doi.org/10.1007/3-540-44612-5_37openalex-snapshot

Alternating and Empty Alternating Auxiliary Stack Automata

inferred← citeshttps://doi.org/10.1007/3-540-44683-4_52openalex-snapshot

From Bidirectionality to Alternation

inferred← citeshttps://doi.org/10.1007/3-540-44968-x_45openalex-snapshot

On the Power of Input-Synchronized Alternating Finite Automata

inferred← citeshttps://doi.org/10.1007/3-540-46093-4_3openalex-snapshot

View-Based Query Answering and Query Containment over Semistructured Data

inferred← citeshttps://doi.org/10.1007/3-540-51498-8_36openalex-snapshot

Representation of recursively enumerable languages using alternating finite tree recognizers

inferred← citeshttps://doi.org/10.1007/3-540-53487-3_38openalex-snapshot

The expressibility of nondeterministic auxiliary stack automata and its relation to treesize bounded alternating auxiliary pushdown automata

inferred← citeshttps://doi.org/10.1007/3-540-54233-7_133openalex-snapshot

Running time to recognize nonregular languages by 2-way probabilistic automata

inferred← citeshttps://doi.org/10.1007/3-540-54458-5_73openalex-snapshot

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

inferred← citeshttps://doi.org/10.1007/3-540-58201-0_59openalex-snapshot

Complexity results for multi-pebble automata and their logics

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-13435-8_4openalex-snapshot

An Oracle Hierarchy for Small One-Way Finite Automata

inferred← citeshttps://doi.org/10.1007/978-3-030-89716-1_1openalex-snapshot

Quantitative vs. Weighted Automata

inferred← citeshttps://doi.org/10.1007/978-3-030-93489-7_8openalex-snapshot

Width Measures of Alternating Finite Automata

inferred← citeshttps://doi.org/10.1007/978-3-032-01475-7_12openalex-snapshot

Improved Upper Bounds for Determinizing NIDPDAs with Limited Nondeterminism

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-58747-9_14openalex-snapshot

Unary Coded PSPACE-Complete Languages in ASPACE(loglog n)

inferred← citeshttps://doi.org/10.1007/978-3-319-90530-3_12openalex-snapshot

Complement for Two-Way Alternating Automata

inferred← citeshttps://doi.org/10.1007/978-3-540-39886-8_12openalex-snapshot

Computational Complexity

inferred← citeshttps://doi.org/10.1007/978-3-540-39886-8_6openalex-snapshot

Pushdown Automata

inferred← citeshttps://doi.org/10.1007/978-3-540-69937-8_6openalex-snapshot

Conjunctive Grammars and Alternating Pushdown Automata

inferred← citeshttps://doi.org/10.1007/978-3-540-88282-4_36openalex-snapshot

On Alternating Phrase-Structure Grammars

inferred← citeshttps://doi.org/10.1007/978-3-642-02737-6_4openalex-snapshot

Size Complexity of Two-Way Finite Automata

inferred← citeshttps://doi.org/10.1007/978-3-642-20169-1_1openalex-snapshot

Linear Conjunctive Grammars and One-Turn Synchronized Alternating Pushdown Automata

inferred← citeshttps://doi.org/10.1007/978-3-642-20712-9_27openalex-snapshot

LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata

inferred← citeshttps://doi.org/10.1007/978-3-642-24897-9_9openalex-snapshot

A Survey on Picture-Walking Automata

inferred← citeshttps://doi.org/10.1007/978-3-642-28717-6_13openalex-snapshot

Finding Finite Herbrand Models

inferred← citeshttps://doi.org/10.1007/978-3-662-44522-8_25openalex-snapshot

Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata

inferred← citeshttps://doi.org/10.1007/978-94-009-2591-5_11openalex-snapshot

Some Additional Remarks

inferred← citeshttps://doi.org/10.1007/bf01185400openalex-snapshot

On the power of 1-tape off-line ATMs running in a bounded number of reversals

inferred← citeshttps://doi.org/10.1007/bf01193576openalex-snapshot

Communication for alternating machines

inferred← citeshttps://doi.org/10.1007/bf01371727openalex-snapshot

State-complexity of finite-state devices, state compressibility and incompressibility

inferred← citeshttps://doi.org/10.1007/bfb0015925openalex-snapshot

Complexity theory and formal languages

inferred← citeshttps://doi.org/10.1007/bfb0015931openalex-snapshot

Some properties of space-bounded synchronized alternating turing machines with only universal states

inferred← citeshttps://doi.org/10.1007/bfb0017175openalex-snapshot

On the power of communication in alternating machines

inferred← citeshttps://doi.org/10.1007/bfb0022666openalex-snapshot

Alternating bottom-up tree recognizers

inferred← citeshttps://doi.org/10.1007/bfb0040374openalex-snapshot

On some languages in NC

inferred← citeshttps://doi.org/10.1007/s00224-018-9844-7openalex-snapshot

Unary Coded PSPACE-Complete Languages in ASPACE(loglog n)

inferred← citeshttps://doi.org/10.1007/s00236-013-0177-3openalex-snapshot

Conjunctive grammars and alternating pushdown automata

inferred← citeshttps://doi.org/10.1007/s00236-020-00373-8openalex-snapshot

Complement for two-way alternating automata

inferred← citeshttps://doi.org/10.1016/0020-0190(92)90119-gopenalex-snapshot

A note on two-way probabilistic automata

inferred← citeshttps://doi.org/10.1016/0020-0190(94)00152-9openalex-snapshot

Refined simulation of multihead automata

inferred← citeshttps://doi.org/10.1016/0022-0000(85)90063-7openalex-snapshot

On the power of alternation in automata theory

inferred← citeshttps://doi.org/10.1016/0022-0000(86)90045-0openalex-snapshot

A lower bound for probabilistic algorithms for finite state machines

inferred← citeshttps://doi.org/10.1016/0022-0000(88)90034-7openalex-snapshot

Relativized alternation and space-bounded computation

inferred← citeshttps://doi.org/10.1016/0022-0000(91)90020-6openalex-snapshot

Properties that characterize LOGCFL

inferred← citeshttps://doi.org/10.1016/0022-0000(92)90045-kopenalex-snapshot

Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations

inferred← citeshttps://doi.org/10.1016/0304-3975(89)90023-6openalex-snapshot

A grammatical characterization of alternating pushdown automata

inferred← citeshttps://doi.org/10.1016/0304-3975(92)90151-5openalex-snapshot

A survey of space complexity

inferred← citeshttps://doi.org/10.1016/0304-3975(92)90355-jopenalex-snapshot

A characterization of exponential-time languages by alternating context-free grammars

inferred← citeshttps://doi.org/10.1016/0890-5401(91)90015-topenalex-snapshot

Iterated stack automata and complexity classes

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

Pushdown module checking with imperfect information

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

Alternating space is closed under complement and other simulations for sublogarithmic space

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

Existential and universal width of alternating finite automata

inferred← citeshttps://doi.org/10.1016/j.jcss.2016.05.008openalex-snapshot

LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata

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

On the complexity of typechecking top-down XML transformations

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

On state-alternating context-free grammars

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

Alternation in two-way finite automata

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

Converting finite width AFAs to nondeterministic and universal finite automata

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

Maximal universal width of an AFA is NP-hard

inferred← citeshttps://doi.org/10.1016/s0019-9958(83)80021-7openalex-snapshot

Tree automata and attribute grammars

inferred← citeshttps://doi.org/10.1016/s0019-9958(84)80029-7openalex-snapshot

Alternation bounded auxiliary pushdown automata

inferred← citeshttps://doi.org/10.1016/s0020-0190(05)80006-7openalex-snapshot

A note on the space complexity of some decision problems for finite automata

inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00326-2openalex-snapshot

Alternating and empty alternating auxiliary stack automata

inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00410-3openalex-snapshot

From bidirectionality to alternation

inferred← citeshttps://doi.org/10.1016/s0304-3975(96)00119-3openalex-snapshot

Complexity results for two-way and multi-pebble automata and their logics

inferred← citeshttps://doi.org/10.1016/s0304-3975(98)00059-0openalex-snapshot

Properties of probabilistic pushdown automata

inferred← citeshttps://doi.org/10.1016/s0898-1221(00)00333-3openalex-snapshot

Lower bounds for multiplayer noncooperative games of incomplete information

inferred← citeshttps://doi.org/10.1051/ita/1988220303191openalex-snapshot

Yield-languages recognized by alternating tree recognizers

inferred← citeshttps://doi.org/10.1051/ita:2001106openalex-snapshot

Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata

inferred← citeshttps://doi.org/10.1051/ita:2005024openalex-snapshot

Complexity results for prefix grammars

inferred← citeshttps://doi.org/10.1093/ietisy/e90-d.6.889openalex-snapshot

Two Ways of Introducing Alternation into Context-Free Grammars and Pushdown Automata

inferred← citeshttps://doi.org/10.1109/istcs.1995.377036openalex-snapshot

Automata with sensing heads

inferred← citeshttps://doi.org/10.1109/sfcs.1989.63522openalex-snapshot

On the power of 2-way probabilistic finite state automata

inferred← citeshttps://doi.org/10.1109/sfcs.1997.646094openalex-snapshot

On the power of quantum finite state automata

inferred← citeshttps://doi.org/10.1137/0215005openalex-snapshot

The Complexity of Languages Generated by Attribute Grammars

inferred← citeshttps://doi.org/10.1137/0219069openalex-snapshot

A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata

inferred← citeshttps://doi.org/10.1137/0220018openalex-snapshot

The Power of Alternating One-Reversal Counters and Stacks

inferred← citeshttps://doi.org/10.1137/0222011openalex-snapshot

${\text{ASPACE}}(o(\log \log n))$ is Regular

inferred← citeshttps://doi.org/10.1137/15m1034714openalex-snapshot

Semantic Acyclicity on Graph Databases

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

ON ALTERNATING PHRASE-STRUCTURE GRAMMARS

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

SPACE HIERARCHIES OF TWO-DIMENSIONAL ALTERNATING TURING MACHINES, PUSHDOWN AUTOMATA AND COUNTER AUTOMATA

inferred← citeshttps://doi.org/10.1145/1013560.1013562openalex-snapshot

Finite state machines for strings over infinite alphabets

inferred← citeshttps://doi.org/10.1145/176584.176588openalex-snapshot

On the power of bounded concurrency II

inferred← citeshttps://doi.org/10.1145/1938551.1938563openalex-snapshot

Artifact systems with data dependencies and arithmetic

inferred← citeshttps://doi.org/10.1145/2338626.2338628openalex-snapshot

Artifact systems with data dependencies and arithmetic

inferred← citeshttps://doi.org/10.1145/2499937.2499940openalex-snapshot

Graph Reachability and Pebble Automata over Infinite Alphabets

inferred← citeshttps://doi.org/10.1145/28395.28411openalex-snapshot

Properties that characterize LOGCFL

inferred← citeshttps://doi.org/10.1145/325694.325730openalex-snapshot

Paths vs. trees in set-based program analysis

inferred← citeshttps://doi.org/10.1145/3576915.3616582openalex-snapshot

Black Ostrich: Web Application Scanning with String Solvers

inferred← citeshttps://doi.org/10.1145/504192.504194openalex-snapshot

SIGACT News complexity theory column 32

inferred← citeshttps://doi.org/10.1145/507457.507465openalex-snapshot

SIGACT news complexity theory column 35

inferred← citeshttps://doi.org/10.1145/800061.808767openalex-snapshot

Iterated pushdown automata and complexity classes

inferred← citeshttps://doi.org/10.22111/ijfs.2016.2360openalex-snapshot

ALTERNATING REGULAR TREE GRAMMARS IN THE FRAMEWORK OF LATTICE-VALUED LOGIC

inferred← citeshttps://doi.org/10.25368/2022.182openalex-snapshot

Finding Finite Herbrand Models

inferred← citeshttps://doi.org/10.37418/amsj.9.11.50openalex-snapshot

FUZZY CONJUNCTIVE GRAMMAR AND FUZZY SYNCHRONIZED ALTERNATING PUSHDOWN AUTOMATA

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

Computational methods for Dynamic Answer Set Programming

inferred← citeshttps://doi.org/10.46298/dmtcs.2138openalex-snapshot

Classical Automata on Promise Problems

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

Graph Reachability and Pebble Automata over Infinite Alphabets

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

Containment of Nested Regular Expressions

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

Context-Free Grammars with Storage

inferred← citeshttps://doi.org/10.7146/brics.v14i13.22178openalex-snapshot

Temporal Logics Beyond Regularity

inferred← citeshttps://doi.org/10.7561/sacs.2023.1.53openalex-snapshot

Maximal Existential and Universal Width

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.