3 citations · 4 across the 4 of their papers we have counts for
4 papers
Note on Undecidability of Bisimilarity for Second-Order Pushdown Processes
Petr Jančar, Jiří Srba
Broadbent and Göller (FSTTCS 2012) proved the undecidability of bisimulation equivalence for processes generated by epsilon-free second-order pushdown automata. We add a few remark…
Equivalence of Deterministic One-Counter Automata is NL-complete
Stanislav Böhm, Stefan Göller, Petr Jančar
We prove that language equivalence of deterministic one-counter automata is NL-complete. This improves the superpolynomial time complexity upper bound shown by Valiant and Paterson…
Bisimilarity of Probabilistic Pushdown Automata
Vojtech Forejt, Petr Jancar, Stefan Kiefer +1
We study the bisimilarity problem for probabilistic pushdown automata (pPDA) and subclasses thereof. Our definition of pPDA allows both probabilistic and non-deterministic branchin…
A Short Decidability Proof for DPDA Language Equivalence via First-Order Grammars
Petr Jancar
The main aim of the paper is to give a short self-contained proof of the decidability of language equivalence for deterministic pushdown automata, which is the famous problem solve…