Vi bevisar att svag bisimilaritet är decidable i polynomial tid mellan nite-state systems och flera klasser av i nite-state systems: context-free processer (BPA) och normed Basic Parallel Processes (normed BPP). Såvitt vi vet är detta de första polynomalgoritmerna för svaga bisimilaritetsproblem som involverar nite-state-system.
Stark och svag bisimilaritet mellan BPA och ändliga-state processer är decidable i polynomial tid REF.
Weak Bisimilarity between Finite-State Systems and BPA or Normed BPP is Decidable in Polynomial Time
{'venue': 'Theoretical Computer Science', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}