3 citations · 4 across the 4 of their papers we have counts for
Showing cs.FLShow all
3 papers · 1 filter
cs.FL2013
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…
cs.FL2012
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…
cs.FL2010★ 3 cited
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…