English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Strong bisimilarity on normed BPA is polynomial-time decidable, while weakbisimilarity on totally normed BPA is NP-hard. It is natural to ask where thecomputational complexity of branching bisimilarity on totally normed BPA lies.This paper confirms that this problem is polynomial-time decidable. To ourknowledge, in the presence of silent transitions, this is the firstbisimilarity checking algorithm on infinite state systems which runs inpolynomial time. This result spots an instance in which branching bisimilarityand weak bisimilarity are both decidable but lie in different complexityclasses (unless NP=P), which is not known before.  The algorithm takes the partition refinement approach and the finalimplementation can be thought of as a generalization of the previous algorithmof Czerwi\'{n}ski and Lasota. However, unexpectedly, the correctness of thealgorithm cannot be directly generalized from previous works, and thecorrectness proof turns out to be subtle. The proof depends on the existence ofa carefully defined refinement operation fitted for our algorithm and theproposal of elaborately developed techniques, which are quite different fromprevious works.

A Polynomial Time Algorithm for Deciding Branching Bisimilarity on Totally Normed BPA