LIPIcs.FSTTCS.2010.260.pdf
- Filesize: 0.52 MB
- 12 pages
Document
Fast equivalence-checking for normed context-free processes
Authors
-
Part of:
Volume:
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2010-12-14
Cite As Get BibTex
Wojciech Czerwinski and Slawomir Lasota. Fast equivalence-checking for normed context-free processes. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 260-271, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/LIPIcs.FSTTCS.2010.260
Abstract
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.
Subject Classification
Keywords
- bisimulation
- norm
- context-free grammar
- simple grammar
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads