Bisimulation Equivalence of First-Order Grammars

DOI10.1007/978-3-662-43951-7_20MaRDI QIDQ5167841zbMATH OpenOpenAlexFDO

Authors Petr Jančar

Publication date 1 July 2014

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.7923

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: A decidability proof for bisimulation equivalence of first-order grammars (finite sets of labelled rules for rewriting roots of first-order terms) is presented. The equivalence generalizes the DPDA (deterministic pushdown automata) equivalence, and the result corresponds to the result achieved by Senizergues (1998, 2005) in the framework of equational graphs, or of PDA with restricted epsilon-steps. The framework of classical first-order terms seems particularly useful for providing a proof that should be understandable for a wider audience. We also discuss an extension to branching bisimilarity, announced by Fu and Yin (2014).

Recommendations

• scientific article; zbMATH DE number 2087495
• scientific article; zbMATH DE number 2020181
• Equivalence of pushdown automata via first-order grammars
• Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence
• Deciding Semantic Finiteness of Pushdown Processes and First-Order Grammars w.r.t. Bisimulation Equivalence.
• Sortal equivalence of bare grammars
• Pushdown Automata and Context-Free Grammars in Bisimulation Semantics
• Pushdown automata and context-free grammars in bisimulation semantics
• Decidability of bisimulation equivalence for process generating context-free languages
• scientific article; zbMATH DE number 4035115

Cited in

(10)

• Equivalence of pushdown automata via first-order grammars
• Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence
• A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
• A completeness result for finite -bisimulations
• Decidability of equivalence of symbolic derivations
• Game characterization of probabilistic bisimilarity, and applications to pushdown automata
• Deciding Semantic Finiteness of Pushdown Processes and First-Order Grammars w.r.t. Bisimulation Equivalence.
• Bisimilarity in Fresh-Register Automata
• The Bisimulation Problem for Equational Graphs of Finite Out-Degree
• Bisimulation equivalence of pushdown automata is Ackermann-complete

This page was built for publication: Bisimulation Equivalence of First-Order Grammars

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