activity
20102013
most citedA Short Decidability Proof for DPDA Language Equivalence via First-Order Grammars

3 citations · 4 across the 4 of their papers we have counts for

collaborators
Showing 2013Show all

2 papers · 1 filter

cs.LO2013★ 1 cited

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…

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…