Buchumschlag

A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Guha, Shibashis, Jecker, Ismaël, Lehtinen, Karoliina, Zimmermann, Martin
Format:	Preprint
Veröffentlicht:	2021
Schlagworte:	Formal Languages and Automata Theory Logic in Computer Science
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

History-deterministic Parikh Automata
von: Erlich, Enzo, et al.
Veröffentlicht: (2022)

Explorability in Pushdown Automata
von: Bedi, Ayaan, et al.
Veröffentlicht: (2025)

Set Automata and Limits of Decidability of Two-Variable Logic on Data Words
von: Guha, Shibashis, et al.
Veröffentlicht: (2026)

Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata
von: Jecker, Ismaël, et al.
Veröffentlicht: (2023)

History-deterministic Timed Automata
von: Bose, Sougata, et al.
Veröffentlicht: (2023)

A Hierarchy of Nondeterminism
von: Radi, Bader Abu, et al.
Veröffentlicht: (2022)

Reachability in 3-VASS is Elementary
von: Czerwiński, Wojciech, et al.
Veröffentlicht: (2025)

Resolving Nondeterminism with Randomness
von: Henzinger, Thomas A., et al.
Veröffentlicht: (2025)

Language Equivalence is Undecidable in VASS with Restricted Nondeterminism
von: Czerwiński, Wojciech, et al.
Veröffentlicht: (2025)

Monitorability for the Modal mu-Calculus over Systems with Data: From Practice to Theory
von: Aceto, Luca, et al.
Veröffentlicht: (2025)

Continuous Pushdown VASS in One Dimension are Easy
von: Perez, Guillermo A., et al.
Veröffentlicht: (2024)

Token Games and History-Deterministic Quantitative-Automata
von: Boker, Udi, et al.
Veröffentlicht: (2021)

The 2-Token Theorem: Recognising History-Deterministic Parity Automata Efficiently
von: Lehtinen, Karoliina, et al.
Veröffentlicht: (2025)

From Muller to Parity and Rabin Automata: Optimal Transformations Preserving (History) Determinism
von: Casares, Antonio, et al.
Veröffentlicht: (2023)

Robust Probabilistic Temporal Logics
von: Zimmermann, Martin
Veröffentlicht: (2023)

Rerailing Automata
von: Ehlers, Rüdiger
Veröffentlicht: (2025)

Tracy, Traces, and Transducers: Computable Counterexamples and Explanations for HyperLTL Model-Checking
von: Winter, Sarah, et al.
Veröffentlicht: (2024)

Prophecies all the Way: Game-based Model-Checking for HyperQPTL beyond $\forall^*\exists^*$
von: Winter, Sarah, et al.
Veröffentlicht: (2025)

Logics for Context-free Hyperproperties
von: Winter, Sarah, et al.
Veröffentlicht: (2026)

The Complexity of Generalized HyperLTL with Stuttering and Contexts
von: Regaud, Gaëtan, et al.
Veröffentlicht: (2025)

Inferring Symbolic Automata
von: Fisman, Dana, et al.
Veröffentlicht: (2021)

Intersecting Dense Automata
von: Chistikov, Dmitry, et al.
Veröffentlicht: (2026)

On Good-for-MDPs Automata
von: Schewe, Sven, et al.
Veröffentlicht: (2022)

Automata on $S$-adic words
von: Berthé, Valérie, et al.
Veröffentlicht: (2025)

Transformers are Inherently Succinct
von: Bergsträßer, Pascal, et al.
Veröffentlicht: (2025)

The $\mathsf{AC}^0$-Complexity Of Visibly Pushdown Languages
von: Göller, Stefan, et al.
Veröffentlicht: (2023)

Variants of Higher-Dimensional Automata
von: Bazille, Hugo, et al.
Veröffentlicht: (2026)

Quantitative Semantics for Jumping Automata
von: Almagor, Shaull, et al.
Veröffentlicht: (2024)

Parikh Automata on Finite and Infinite Words
von: Grobler, Mario, et al.
Veröffentlicht: (2023)

Knowledge Compilation for Quantification in Alternating Automata
von: Akshay, S., et al.
Veröffentlicht: (2026)

Logic and Languages of Higher-Dimensional Automata
von: Amrane, Amazigh, et al.
Veröffentlicht: (2024)

Arbitrary-arity Tree Automata and QCTL
von: Laroussinie, François, et al.
Veröffentlicht: (2024)

Bisimulations and Logics for Higher-Dimensional Automata
von: Zouari, Safa, et al.
Veröffentlicht: (2024)

The Complexity of Second-order HyperLTL
von: Frenkel, Hadar, et al.
Veröffentlicht: (2023)

Decision Questions for Probabilistic Automata on Small Alphabets
von: Bell, Paul C., et al.
Veröffentlicht: (2021)

Determinization of Min-Plus Weighted Automata is Decidable
von: Almagor, Shaull, et al.
Veröffentlicht: (2025)

How Concise are Chains of co-Büchi Automata?
von: Ehlers, Rüdiger
Veröffentlicht: (2026)

Invariants for One-Counter Automata with Disequality Tests
von: Chistikov, Dmitry, et al.
Veröffentlicht: (2024)

Feasability of Learning Weighted Automata on a Semiring
von: Daviaud, Laure, et al.
Veröffentlicht: (2023)

Discounted-Sum Automata with Multiple Discount Factors
von: Boker, Udi, et al.
Veröffentlicht: (2023)