31 citations · 56 across the 19 of their papers we have counts for
4 papers · 1 filter
Simplest Non-Regular Deterministic Context-Free Language
Petr Jancar, Jiri Sima
We introduce a new notion of C-simple problems for a class C of decision problems (i.e. languages), w.r.t. a particular reduction. A problem is C-simple if it can be reduced to eac…
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…