A bialgebraic approach to automata and formal language theory

DOI10.1016/J.APAL.2011.09.019zbMATH Open1241.18004arXiv0807.4553OpenAlexW2083840254MaRDI QIDQ408529FDOQ408529

Authors: J. Worthington 

Publication date: 10 April 2012

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

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.

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

Recommendations

• A Bialgebraic Approach to Automata and Formal Language Theory
• A Bialgebraic Review of Deterministic Automata, Regular Expressions and Languages
• Algebraic Theory of Automata and Languages
• scientific article; zbMATH DE number 3250570
• scientific article; zbMATH DE number 3390671
• Algebras, automata and logic for languages of labeled birooted trees
• scientific article; zbMATH DE number 704484
• Automata algebras
• Automata and algebraicity
• scientific article; zbMATH DE number 194781

zbMATH Keywords

automatanondeterminismsemimodulebialgebra\(K\)-linear automata

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Universal coalgebra: A theory of systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bisimulation relations for weighted automata
• Title not available (Why is that?)
• A completeness theorem for Kleene algebras and the algebra of regular events
• Tensor products of idempotent semimodules. An algebraic approach
• Title not available (Why is that?)
• Title not available (Why is that?)
• Automatic Proof Generation in Kleene Algebra
• The realization of input-output maps using bialgebras
• Title not available (Why is that?)
• Title not available (Why is that?)
• Direct and dual laws for automata with multiplicities

Cited In (9)

• Language acceptability of finite automata based on theory of semi‐tensor product of matrices
• A CATEGORICAL APPROACH TO ALGEBRAS AND COALGEBRAS
• A Bialgebraic Review of Deterministic Automata, Regular Expressions and Languages
• Hopf Semialgebras
• Deterministic biautomata and subclasses of deterministic linear languages
• Title not available (Why is that?)
• Semicorings and Semicomodules
• A Bialgebraic Approach to Automata and Formal Language Theory
• Title not available (Why is that?)

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)