Fast equivalence-checking for normed context-free processes

DOI10.4230/LIPICS.FSTTCS.2010.260MaRDI QIDQ2908855zbMATH OpenFDO

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

zbMATH Keywords

bisimulationcontext-free grammarnormsimple 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)

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

Cited in

(10)

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

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)