6533b850fe1ef96bd12a837a
RESEARCH PRODUCT
Varieties and Covarieties of Languages (Extended Abstract)
Enric Cosme LlópezAdolfo Ballester-bolinchesJan Ruttensubject
Discrete mathematicsGeneral Computer ScienceCoalgebraData ScienceStructure (category theory)Duality (optimization)equationalgebraAutomataTheoretical Computer ScienceAlgebravarietyReachabilityDeterministic automatonComputingMethodologies_DOCUMENTANDTEXTPROCESSINGcoequationObservabilityIsomorphismcovarietyVariety (universal algebra)coalgebraComputer Science::Formal Languages and Automata TheoryComputer Science(all)Mathematicsdescription
AbstractBecause of the isomorphism (X×A)→X≅X→(A→X), the transition structure of a deterministic automaton with state set X and with inputs from an alphabet A can be viewed both as an algebra and as a coalgebra. This algebra-coalgebra duality goes back to Arbib and Manes, who formulated it as a duality between reachability and observability, and is ultimately based on Kalmanʼs duality in systems theory between controllability and observability. Recently, it was used to give a new proof of Brzozowskiʼs minimization algorithm for deterministic automata. Here we will use the algebra-coalgebra duality of automata as a common perspective for the study of both varieties and covarieties, which are classes of automata and languages defined by equations and coequations, respectively. We make a first connection with Eilenbergʼs definition of varieties of languages, which is based on the classical, algebraic notion of varieties of (transition) monoids.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2013-11-01 | Electronic Notes in Theoretical Computer Science |