Fast equivalence-checking for normed context-free processes

DOI10.4230/LIPICS.FSTTCS.2010.260zbMATH Open1245.68134MaRDI QIDQ2908855FDOQ2908855

Authors: Wojciech Czerwiński, Sławomir Lasota 

Publication date: 29 August 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_755d.html

Recommendations

• Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• Bisimulation equivalence is decidable for all context-free processes
• Deciding bisimilarity of normed context-free processes is in \(\Sigma_ 2^ p\)
• Decidability of bisimulation equivalence for process generating context-free languages

zbMATH Keywords

normcontext-free grammarbisimulationsimple grammar

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cited In (9)

• Equivalence of pushdown automata via first-order grammars
• Partially-commutative context-free processes: expressibility and tractability
• Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes
• Language equivalence of probabilistic pushdown automata
• Bisimulation equivalence and regularity for real-time one-counter automata
• The complexity of compressed membership problems for finite automata
• Deciding the bisimilarity of context-free session types
• Partially-Commutative Context-Free Processes
• Decidability of bisimulation equivalence for process generating context-free languages

This page was built for publication: Fast equivalence-checking for normed context-free processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2908855)