Search

• < Previous
• 1
• Next >

---

Bisimilarity on Basic Process Algebra is in 2-ExpTime (an explicit proof)

Petr Jancar.

Burkart, Caucal, Steffen (1995) showed a procedure deciding bisimulation equivalence of processes in Basic Process Algebra (BPA), i.e. of sequential processes generated by context-free grammars. They improved the previous decidability result of Christensen, H\"uttel, Stirling (1992), since their&nbsp;[&hellip;]

---

Countdown games, and simulation on (succinct) one-counter nets

Petr Jancar ; Petr Osicka ; Zdenek Sawa.

We answer an open complexity question by Hofman, Lasota, Mayr, Totzke (LMCS 2016) for simulation preorder on the class of succinct one-counter nets (i.e., one-counter automata with no zero tests where counter increments and decrements are integers written in binary); the problem was known to be&nbsp;[&hellip;]

---