2026-07-22T14:19:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2869 2024-03-06T10:33:38Z ddc:004 open_access

Fast equivalence-checking for normed context-free processes Czerwinski, Wojciech Lasota, Slawomir bisimulation norm context-free grammar simple grammar Bisimulation equivalence is decidable in polynomial time over normed graphs generated by a context-free grammar. We present a new algorithm, working in time $O(n^5)$, thus improving the previously known complexity $O(n^8 * polylog(n))$. It also improves the previously known complexity $O(n^6 * polylog(n))$ of the equality problem for simple grammars. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Wojciech Czerwinski and Slawomir Lasota 2010 Is Part Of LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2010.260 urn:nbn:de:0030-drops-28690 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.260 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode