A polynomial algorithm for deciding bisimilarity of normed context-free processes
From MaRDI portal
Publication:1351456
DOI10.1016/0304-3975(95)00064-XzbMath0871.68086WikidataQ59556999 ScholiaQ59556999MaRDI QIDQ1351456
Faron Moller, Joram Hirschfeld, Mark R. Jerrum
Publication date: 27 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
Equality Testing of Compressed Strings, Grammar-Based Tree Compression, Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines, Bisimulation equivalence and regularity for real-time one-counter automata, Partially-Commutative Context-Free Processes, Prime normal form and equivalence of simple grammars, Equivalence of simple functions, A generic framework for checking semantic equivalences between pushdown automata and finite-state automata, Parallel Identity Testing for Skew Circuits with Big Powers and Applications, High undecidability of weak bisimilarity for Petri nets, REDUCING SIMPLE GRAMMARS: EXPONENTIAL AGAINST HIGHLY-POLYNOMIAL TIME IN PRACTICE, Infinite results, The complexity of bisimilarity-checking for one-counter processes., Undecidability of domino games and hhp-bisimilarity., Space-efficient scheduling of stochastically generated tasks, Equivalence of pushdown automata via first-order grammars, Complexity of deciding bisimilarity between normed BPA and normed BPP, Selected Ideas Used for Decidability and Undecidability of Bisimilarity, Deciding Bisimilarity of Full BPA Processes Locally, Normed BPA vs. Normed BPP Revisited, Unnamed Item, Deciding the Bisimilarity of Context-Free Session Types, Complexity of Weak Bisimilarity and Regularity for BPA and BPP, Language equivalence of probabilistic pushdown automata, Partially-commutative context-free processes: expressibility and tractability, Weak bisimilarity and regularity of context-free processes is EXPTIME-hard, On the computational complexity of bisimulation, redux, Pushdown automata, multiset automata, and Petri nets, On the complexity of checking semantic equivalences between pushdown processes and finite-state processes, COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA, A general approach to comparing infinite-state systems with their finite-state specifications, Bisimulation and coinduction enhancements: a historical perspective, Parallel identity testing for skew circuits with big powers and applications, Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time, Inter-procedural Two-Variable Herbrand Equalities, Effective decomposability of sequential behaviours, Complete formal systems for equivalence problems, \(L(A)=L(B)\)? decidability results from complete formal systems, Compression techniques in group theory
Cites Work
- Algebra of communicating processes with abstraction
- Unique decomposition of processes
- The polynomial-time hierarchy
- Deciding bisimilarity of normed context-free processes is in \(\Sigma_ 2^ p\)
- Decidability of bisimulation equivalence for process generating context-free languages
- Graphes canoniques de graphes algébriques
- Description of developmental languages using recurrence systems
- Fast Pattern Matching in Strings
- A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
- A fast algorithm to decide on the equivalence of stateless DPDA
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
