The dual equivalence of equations and coequations for automata
type: Item
instance of: scholarly article
title: The dual equivalence of equations and coequations for automata
zbMATH Open document ID: 1333.68184
author: Adolfo Ballester-Bolinches
author: Enric Cosme-Llópez
author: Jan J. M. M. Rutten
published in: Information and Computation
publication date: 2015-09-28T00:00:00Z
review text: This article investigates deterministic (potentially infinite-state) automata from a category-theoretic perspective. The basis of each automaton, its transition system, is an algebra and a co-algebra. Adding an initial state preserves the algebra structure, but adding a set of final states only preserves the co-algebra structure. In the following, let \(A = (Q, \Sigma, \delta)\) be a transition system with (potentially infinite) sets \(Q\) and \(\Sigma\) and transition function \(\delta : Q \times \Sigma \to Q\). Each choice \(q \in Q\) of an initial state determines a unique homomorphism \(h_q : \Sigma^* \to Q\), namely the one that given an input \(w \in \Sigma^*\) assigns the state reached after reading \(w\) starting from \(q\) in the transition system \(A\). A set \(E\) of equations for \(A\) is defined to be a bisimulation equivalence \(E\) on \(\Sigma^*\) (i.e., an equivalence such that for every \((v, w) \in E\) also \((v\sigma, w\sigma) \in E\) for all \(\sigma \in \Sigma\)) such that \(h_q(v) = h_q(w)\) for all \((v, w) \in E\) and \(q \in Q\). In other words, if the words \(v\) and \(w\) are in relation, then no matter at which initial state we start we need to reach the same state processing \(v\) and \(w\). The transition structure \(\operatorname{free}(A)\) is the product of the automata \((A_q)_{q \in Q}\), where \(A_q\) is the transition structure \(A\) together with the initial state \(q\), factored by the kernel \(K\) of its reachability map. It is demonstrated that the kernel \(K\) is the largest set of equations for \(A\). Similarly, a set of co-equations is a subautomaton of the automaton of right languages such that the right language of each state \(q \in Q\) is contained for each choice of final states \(F \subseteq Q\). A co-product construction yields the automaton \(\operatorname{cofree}(A)\) representing the smallest set of co-equations for \(A\). Both constructions are actually functorial. Furthermore it is demonstrated that certain natu…
reviewed by: Andreas Maletti
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 18A30
Mathematics Subject Classification ID: 18A32
zbMATH DE Number: 6485810
zbMATH Keywords: transition system
zbMATH Keywords: automaton
zbMATH Keywords: algebra
zbMATH Keywords: coalgebra
zbMATH Keywords: dual equivalence
zbMATH Keywords: syntactic monoid
zbMATH Keywords: equation
zbMATH Keywords: coequation
MaRDI profile type: Publication
full work available at URL: j.ic.2015.08.001
OpenAlex ID: W2123724019
cites work: Q4079524
cites work: Q4132170
cites work: Q4251915
cites work: Universal coalgebra: A theory of systems
cites work: Q3644388
cites work: Q5762080
cites work: On the relevance of abstract algebra to control theory
cites work: Adjoint machines, state-behavior machines, and duality
cites work: Q5638871
cites work: Brzozowski’s Algorithm (Co)Algebraically
cites work: Algebra-coalgebra duality in brzozowski's minimization algorithm
cites work: Derivatives of Regular Expressions
cites work: Varieties of Languages in a Category
cites work: Q5541339
cites work: Duality and Recognition
cites work: Q4206797
cites work: Q4848740
cites work: Regular languages and Stone duality
cites work: Stone Duality and the Recognisable Languages over an Algebra
cites work: Duality and Equational Theory of Regular Languages
cites work: Q3735051
cites work: On finite monoids having only trivial subgroups
cites work: Q4077455
cites work: Q3044353
cites work: Q4439449
cites work: Some properties of disjunctive languages on a free monoid
cites work: Q3364262
cites work: Q5599198
cites work: Varieties of groups
cites work: Q5459443
cites work: Q3769981
cites work: Checking NFA equivalence with bisimulations up to congruence
cites work: Formations of finite monoids and formal languages: Eilenberg's variety theorem revisited.
cites work: The Birkhoff theorem for finite algebras
cites work: Q5302760
cites work: Varieties and covarieties of languages (extended abstract)
cites work: Minimization via Duality
cites work: Generalized Eilenberg Theorem I: Local Varieties of Languages
DOI: 10.1016/J.IC.2015.08.001
description: scientific article; zbMATH DE number 6485810