Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
3 results

Game Characterization of Probabilistic Bisimilarity, and Applications to Pushdown Automata

Vojtěch Forejt ; Petr Jančar ; Stefan Kiefer ; James Worrell.
We study the bisimilarity problem for probabilistic pushdown automata (pPDA) and subclasses thereof. Our definition of pPDA allows both probabilistic and non-deterministic branching, generalising the classical notion of pushdown automata (without epsilon-transitions). We first show a general&nbsp;[&hellip;]
Published on November 15, 2018
Volume 14, Issue 4

Bisimilarity on Basic Process Algebra is in 2-ExpTime (an explicit proof)

Petr Jancar.
Burkart, Caucal, Steffen (1995) showed a procedure deciding bisimulation equivalence of processes in Basic Process Algebra (BPA), i.e. of sequential processes generated by context-free grammars. They improved the previous decidability result of Christensen, H\"uttel, Stirling (1992), since their&nbsp;[&hellip;]
Published on March 13, 2013
Volume 9, Issue 1

Branching Bisimilarity of Normed BPA Processes as a Rational Monoid

Petr Jancar.
The paper presents an elaborated and simplified version of the structural result for branching bisimilarity on normed BPA (Basic Process Algebra) processes that was the crux of a conference paper by Czerwinski and Jancar (arxiv 7/2014 and LiCS 2015). That paper focused on the computational&nbsp;[&hellip;]
Published on November 28, 2017
Volume 13, Issue 4
  • < Previous
  • 1
  • Next >