KUČERA, Antonín a Richard MAYR. Weak Bisimilarity between Finite-State Systems and BPA or normed BPP is Decidable in Polynomial Time. Theoretical Computer Science. Amsterdam, Nizozemí, 2002, roč. 270, 1-2, s. 677-700. ISSN 0304-3975. |
Další formáty:
BibTeX
LaTeX
RIS
@article{376211, author = {Kučera, Antonín and Mayr, Richard}, article_location = {Amsterdam, Nizozemí}, article_number = {1-2}, keywords = {concurrency; infinite-state systems; bisimilarity}, language = {eng}, issn = {0304-3975}, journal = {Theoretical Computer Science}, title = {Weak Bisimilarity between Finite-State Systems and BPA or normed BPP is Decidable in Polynomial Time}, volume = {270}, year = {2002} }
TY - JOUR ID - 376211 AU - Kučera, Antonín - Mayr, Richard PY - 2002 TI - Weak Bisimilarity between Finite-State Systems and BPA or normed BPP is Decidable in Polynomial Time JF - Theoretical Computer Science VL - 270 IS - 1-2 SP - 677 EP - 677 SN - 03043975 KW - concurrency KW - infinite-state systems KW - bisimilarity N2 - We prove that weak bisimilarity is decidable in polynomial time between finite-state systems and several classes of infinite-state systems: context-free processes (BPA) and normed Basic Parallel Processes (normed BPP). To the best of our knowledge, these are the first polynomial algorithms for weak bisimilarity problems involving infinite-state systems. ER -
KUČERA, Antonín a Richard MAYR. Weak Bisimilarity between Finite-State Systems and BPA or normed BPP is Decidable in Polynomial Time. \textit{Theoretical Computer Science}. Amsterdam, Nizozemí, 2002, roč.~270, 1-2, s.~677-700. ISSN~0304-3975.
|