Checking NFA equivalence with bisimulations up to congruence

DOI10.1145/2429069.2429124zbMath1301.68169OpenAlexW2007281030MaRDI QIDQ2931822

Damien Pous, Filippo Bonchi

Publication date: 27 November 2014

Published in: Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2429069.2429124

zbMATH Keywords

automataantichainbisimulationcongruencelanguage equivalencecoinductionup-to techniques

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items

Coinductive predicates and final sequences in a fibration, A symbolic decision procedure for symbolic alternating finite automata, Algorithms for Kleene algebra with converse, Nominal Kleene Coalgebra, Final Semantics for Decorated Traces, Unnamed Item, A theoretical framework for cardinality-based feature models: the semantics and computational aspects, Manipulation of regular expressions using derivatives: an overview, Completeness and incompleteness in nominal Kleene algebra, Extracting Proofs from Tabled Proof Search, Width of Non-deterministic Automata, Deciding Synchronous Kleene Algebra with Derivatives, Proving language inclusion and equivalence by coinduction, Formal methods for NFA equivalence: QBFs, witness extraction, and encoding verification, Unnamed Item, Unnamed Item, Enhanced coalgebraic bisimulation, Up-to techniques for behavioural metrics via fibrations, Verified decision procedures for MSO on words based on derivatives of regular expressions, Unnamed Item, Fair Termination for Parameterized Probabilistic Concurrent Systems, Up-To Techniques for Weighted Systems, The dual equivalence of equations and coequations for automata, Up-To Techniques for Behavioural Metrics via Fibrations, Coinductive Algorithms for Büchi Automata, A general account of coinduction up-to, Automata Learning: A Categorical Perspective, Unnamed Item, Unnamed Item, Bisimulation and coinduction enhancements: a historical perspective, (in)finite trace equivalence of probabilistic transition systems, Unnamed Item, Equations, Contractions, and Unique Solutions, Abstraction refinement and antichains for trace inclusion of infinite state systems, Robust biomolecular finite automata, Coinductive predicates and final sequences in a fibration, Mechanized metatheory revisited, Unnamed Item, Coalgebraic semantics for nominal automata