Game characterization of probabilistic bisimilarity, and applications to pushdown automata

Game characterization of probabilistic bisimilarity, and applications to pushdown automata

We study the bisimilarity problem for probabilistic pushdown automata (pPDA) and subclasses thereof. Our definition of pPDA allows both probabilistic and nondeterministic branching, generalising the classical notion of pushdown automata (without epsilon-transitions). We first show a general characte...

Mô tả đầy đủ

Chi tiết về thư mục
Những tác giả chính:	Forejt, V, Jancar, P, Kiefer, S, Worrell, J
Định dạng:	Journal article
Được phát hành:	International Federation of Computational Logic 2018

Những quyển sách tương tự

Game Characterization of Probabilistic Bisimilarity, and Applications to Pushdown Automata
Bằng: Vojtěch Forejt, et al.
Được phát hành: (2018-11-01)

Branching-Time Model-Checking of Probabilistic Pushdown Automata.
Bằng: Brázdil, T, et al.
Được phát hành: (2009)

The Complexity of Computing a Bisimilarity Pseudometric on Probabilistic Automata
Bằng: van Breugel, F, et al.
Được phát hành: (2014)

Computing probabilistic bisimilarity distances for probabilistic automata
Bằng: Bacci, G, et al.
Được phát hành: (2021)

Computing Probabilistic Bisimilarity Distances for Probabilistic Automata
Bằng: Giorgio Bacci, et al.
Được phát hành: (2021-02-01)

Lattice structures for bisimilar Probabilistic Automata
Bằng: Johann Schuster, et al.
Được phát hành: (2014-02-01)

Deciding probabilistic bisimilarity distance one for probabilistic automata
Bằng: Tang, Q, et al.
Được phát hành: (2020)

Model Checking Probabilistic Pushdown Automata
Bằng: Javier Esparza, et al.
Được phát hành: (2006-03-01)

On the Complexity of Computing Probabilistic Bisimilarity
Bằng: Chen, D, et al.
Được phát hành: (2012)

Minimising the probabilistic bisimilarity distance
Bằng: Kiefer, S, et al.
Được phát hành: (2024)

Good-for-games $\omega$-Pushdown Automata
Bằng: Karoliina Lehtinen, et al.
Được phát hành: (2023-02-01)

Reachability in pushdown register automata
Bằng: Murawski, A, et al.
Được phát hành: (2017)

Edit Distance for Pushdown Automata
Bằng: Krishnendu Chatterjee, et al.
Được phát hành: (2017-09-01)

Adding Time to Pushdown Automata
Bằng: Parosh Aziz Abdulla, et al.
Được phát hành: (2012-12-01)

Zenoness for Timed Pushdown Automata
Bằng: Parosh Aziz Abdulla, et al.
Được phát hành: (2014-02-01)

Bounded-oscillation Pushdown Automata
Bằng: Pierre Ganty, et al.
Được phát hành: (2016-09-01)

Collapsible Pushdown Automata and Recursion Schemes
Bằng: Murawski, C, et al.
Được phát hành: (2008)

Collapsible pushdown automata and recursion schemes
Bằng: Hague, M, et al.
Được phát hành: (2017)

Collapsible pushdown automata and recursion schemes
Bằng: Hague, M, et al.
Được phát hành: (2008)

Pushdown Automata in Statistical Machine Translation
Bằng: Cyril Allauzen, et al.
Được phát hành: (2023-07-01)

On the Existence of Universal Finite or Pushdown Automata
Bằng: Manfred Kudlek
Được phát hành: (2012-07-01)

On Tree Pattern Matching by Pushdown Automata
Bằng: T. Flouri
Được phát hành: (2009-01-01)

Codensity games for bisimilarity
Bằng: Komorida, Y, et al.
Được phát hành: (2022)

Language equivalence for probabilistic automata
Bằng: Kiefer, S, et al.
Được phát hành: (2011)

Expected-Delay-Summing Weak Bisimilarity for Markov Automata
Bằng: Alessandro Aldini, et al.
Được phát hành: (2015-09-01)

On the Complexity of the Equivalence Problem for Probabilistic Automata
Bằng: Kiefer, S, et al.
Được phát hành: (2012)

On collapsible pushdown automata, their graphs and the power of links
Bằng: Broadbent, C, et al.
Được phát hành: (2011)

Minimization of visibly pushdown automata is NP-complete
Bằng: Olivier Gauwin, et al.
Được phát hành: (2020-02-01)

Beyond Language Equivalence on Visibly Pushdown Automata
Bằng: Jiří Srba
Được phát hành: (2009-01-01)

Reachability Problem for Weak Multi-Pushdown Automata
Bằng: Wojciech Czerwiński, et al.
Được phát hành: (2013-09-01)

Model-Checking of Ordered Multi-Pushdown Automata
Bằng: Mohamed Faouzi Atig
Được phát hành: (2012-09-01)

Input-Driven Double-Head Pushdown Automata
Bằng: Markus Holzer, et al.
Được phát hành: (2017-08-01)

Simulation of Two-Way Pushdown Automata Revisited
Bằng: Robert Glück
Được phát hành: (2013-09-01)

Unboundedness and downward closures of higher-order pushdown automata
Bằng: Hague, M, et al.
Được phát hành: (2016)

Branching Bisimilarity of Normed BPA Processes as a Rational Monoid
Bằng: Petr Jancar
Được phát hành: (2017-11-01)

A Fragment of ML Decidable by Visibly Pushdown Automata
Bằng: Hopkins, D, et al.
Được phát hành: (2011)

On the Expressive Power of 2-Stack Visibly Pushdown Automata
Bằng: Benedikt Bollig
Được phát hành: (2008-12-01)

Pushdown Automata and Context-Free Grammars in Bisimulation Semantics
Bằng: Jos C. M. Baeten, et al.
Được phát hành: (2023-03-01)

Serializing the Parallelism in Parallel Communicating Pushdown Automata Systems
Bằng: M. Sakthi Balan
Được phát hành: (2009-07-01)

The Triple-Pair Construction for Weighted ω-Pushdown Automata
Bằng: Manfred Droste, et al.
Được phát hành: (2017-08-01)