A bialgebraic approach to automata and formal language theory

DOI10.1016/J.APAL.2011.09.019MaRDI QIDQ408529zbMATHOpenAlexFDO

Publication date 10 April 2012

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

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

automata nondeterminism semimodule bialgebra \(K\)-linear automata

Algebraic theory of languages and automata (68Q70) Applications of universal algebra in computer science (08A70) Categories of machines, automata (18B20)

Abstract: A bialgebra is a structure which is simultaneously an algebra and a coalgebra, such that the algebraic and coalgebraic parts are "compatible". Bialgebras are normally studied over a field or commutative ring. In this paper, we show how to apply the defining diagrams of algebras, coalgebras, and bialgebras to categories of semimodules and semimodule homomorphisms over a commutative semiring. We then show that formal language theory and the theory of bialgebras have essentially undergone "convergent evolution", with the same constructions appearing in both contexts. For example, formal languages correspond to elements of dual algebras of coalgebras, automata are "pointed representation objects" of algebras, automaton morphisms are instances of linear intertwiners, and a construction from the theory of bialgebras shows how to run two automata in parallel. We also show how to associate an automaton with an arbitrary algebra, which in the classical case yields the automaton whose states are formal languages and whose transitions are given by language differentiation.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: A bialgebraic approach to automata and formal language theory

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