Bisimulation equivalence and regularity for real-time one-counter automata

作者：

Highlights：

• Bisimulation equivalence is PSPACE-complete for real-time one-counter automata.

• Language equivalence is NL-complete for deterministic real-time one-counter automata.

• Finiteness w.r.t. bisimilarity is P-complete for real-time one-counter automata.

• Regularity is NL-complete for deterministic real-time one-counter automata.

摘要

•Bisimulation equivalence is PSPACE-complete for real-time one-counter automata.•Language equivalence is NL-complete for deterministic real-time one-counter automata.•Finiteness w.r.t. bisimilarity is P-complete for real-time one-counter automata.•Regularity is NL-complete for deterministic real-time one-counter automata.

论文关键词：One-counter automaton,Bisimulation equivalence,Language equivalence,Regularity

论文评审过程：Received 30 July 2012, Revised 3 October 2013, Accepted 22 November 2013, Available online 1 December 2013.

论文官网地址：https://doi.org/10.1016/j.jcss.2013.11.003