Probabilistic input-driven pushdown automata

DOI10.1016/J.IC.2025.105312MaRDI QIDQ6966435zbMATH OpenFDO

Authors Alex Rose, Alexander Okhotin

Publication date 27 June 2025

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2025.105312

zbMATH Keywords

probabilistic automatafinite automatastate complexityvisibly pushdown automatainput-driven automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• scientific article; zbMATH DE number 3885334 (Why is no real title available?)
• scientific article; zbMATH DE number 3572058 (Why is no real title available?)
• scientific article; zbMATH DE number 1747446 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• Adding nesting structure to words
• Alternating Automata and a Temporal Fixpoint Calculus for Visibly Pushdown Languages
• Automata, Languages and Programming
• Bracket-languages are recognizable in logarithmic space
• Descriptional complexity of unambiguous input-driven pushdown automata
• Diagnosis in infinite-state probabilistic systems
• Event-Clock Visibly Pushdown Automata
• Event-clock nested automata
• Exact descriptional complexity of determinization of input-driven pushdown automata
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Game characterization of probabilistic bisimilarity, and applications to pushdown automata
• Input-driven pushdown automata on well-nested infinite strings
• Language recognition using probabilistic Turing machines in real time, and automata with a push-down store
• Model checking temporal properties of recursive probabilistic programs
• NON-CONSTRUCTIVE METHODS FOR FINITE PROBABILISTIC AUTOMATA
• Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
• On dominance and varieties of commuting matrices
• On probabilistic pushdown automata
• On the determinization of event-clock input-driven pushdown automata
• On the size of unary probabilistic and nondeterministic automata
• One-way bounded-error probabilistic pushdown automata and Kolmogorov complexity (preliminary report)
• Probabilistic automata
• The complexity of probabilistic versus deterministic finite automata
• Tinput-driven pushdown, counter, and stack automata
• Two-way visibly pushdown automata and transducers
• Visibly pushdown languages

This page was built for publication: Probabilistic input-driven pushdown automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6966435)