Bisimulation of automata
type: Item
instance of: scholarly article
title: Bisimulation of automata
zbMATH Open document ID: 0679.68111
DOI: 10.1016/0890-5401(88)90017-X
author: David B. Benson
author: Ofer Ben-Shachar
published in: Information and Computation
publication date: 1988-01-01T00:00:00Z
review text: The authors give an algebraic characterization of automata and discuss various types of simulation between them. Their environment is the category PureAut whose objects are so-called incompletely-specified nondeterministic input-only automata with a set of pure states, and whose morphisms are given by certain maps between the sets of pure states. Thus PureAut may be viewed as a non-full subcategory of Set which is shown to be cocomplete and to have epi-mono factorizations. \{The authors do not always use categorical terminology consequently. For instance, they define pure epimorphisms to be those morphisms which are induced by surjections, without clarifying that these are the epimorphisms in PureAut. But this very fact is used when they claim that pure epimorphisms are stable under pushout.\}
reviewed by: Walter Tholen
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 18B20
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4114035
zbMATH Keywords: automaton
zbMATH Keywords: pure epimorphism
zbMATH Keywords: (weak) bisimulation
MaRDI profile type: Publication
cites work: Machines in a Category: An Expository Introduction
cites work: An abstract machine theory for formal language parsers
cites work: The inverse semigroup of a sum-ordered semiring
cites work: Fixed points in free process algebras. I
cites work: Process algebra for synchronous communication
cites work: Algebra of communicating processes with abstraction
cites work: Q3742698
cites work: Q3677164
cites work: Categories of semimodules: The categorical structural properties of transition systems
cites work: Realization is universal
cites work: Q3956373
cites work: Algebraic laws for nondeterminism and concurrency
cites work: Q3877831
cites work: Q3777424
cites work: On modules over a semiring
cites work: Q3704880
cites work: Q4123496
cites work: Functional behavior of nondeterministic and concurrent programs
cites work: Q3687683
cites work: Q4065458
cites work: A calculus of communicating systems
cites work: Calculi for synchrony and asynchrony
description: scientific article; zbMATH DE number 4114035