31 citations · 56 across the 19 of their papers we have counts for
4 papers · 1 filter
Bisimulation equivalence of first-order grammars is Ackermann-hard
Petr Jancar
Bisimulation equivalence (or bisimilarity) of first-order grammars is decidable, as follows from the decidability result by Senizergues (1998, 2005) that has been given in an equiv…
Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence
Petr Jancar
The problem if a given configuration of a pushdown automaton (PDA) is bisimilar with some (unspecified) finite-state process is shown to be decidable. The decidability is proven in…
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…