Bisimulation equivalence is decidable for one-counter processes

<a class="pub-badge pub-badge--doi" href="https://doi.org/10.1007/3-540-63165-8_210" rel="nofollow">DOI 10.1007/3-540-63165-8_210</a><a class="pub-badge pub-badge--grey" href="https://zbmath.org/1401.68229" rel="nofollow">zbMATH</a><a class="pub-badge pub-badge--grey" href="https://openalex.org/works/W1525520647" rel="nofollow">OpenAlex</a><a class="pub-badge pub-badge--mardi" href="https://portal.mardi4nfdi.de/wiki/Item:Q4571985" rel="nofollow">MaRDI QID Q4571985</a><a class="pub-badge pub-badge--grey" href="https://fdo.portal.mardi4nfdi.de/fdo/Q4571985" rel="nofollow">FDO</a>

Authors Petr Jančar

Publication date 4 July 2018

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-63165-8_210

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Decidability of bisimilarity for one-counter processes.
• Bisimulation equivalence is decidable for all context-free processes
• scientific article; zbMATH DE number 2038739
• scientific article; zbMATH DE number 1500527
• The complexity of bisimilarity-checking for one-counter processes.
• Bisimilarity of one-counter processes is PSPACE-complete
• Decidability of bisimulation equivalence for process generating context-free languages
• scientific article; zbMATH DE number 4035115
• Computable processes and bisimulation equivalence
• Deciding bisimulation-like equivalences with finite-state processes

Cites work

• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 1555184 (Why is no real title available?)
• scientific article; zbMATH DE number 2102771 (Why is no real title available?)
• Bisimulation collapse and the process taxonomy
• Bisimulation equivalence is decidable for all context-free processes
• Decidability of bisimulation equivalence for normed pushdown processes
• Petri nets, commutative context-free grammars, and basic parallel processes
• Semigroups, Presburger formulas, and languages
• Undecidability of bisimilarity for Petri nets and some related problems

Cited in

(9)

• Complete formal systems for equivalence problems
• Basic process algebra with deadlocking states
• Deciding bisimulation and trace equivalences for systems with many identical processes
• Deciding bisimulation and trace equivalences for systems with many identical processes
• scientific article; zbMATH DE number 2038739 (Why is no real title available?)
• \(L(A)=L(B)\)? decidability results from complete formal systems
• Bisimilarity of one-counter processes is PSPACE-complete
• Regularity of normed PA processes
• Decidability of bisimilarity for one-counter processes.

This page was built for publication: Bisimulation equivalence is decidable for one-counter processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4571985)