We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A FINITE AXIOMATISATION OF FINITE-STATE AUTOMATA USING STRING DIAGRAMS.
- Authors
PIEDELEU, ROBIN; ZANASI, FABIO
- Abstract
We develop a fully diagrammatic approach to finite-state automata, based on reinterpreting their usual state-transition graphical representation as a two-dimensional syntax of string diagrams. In this setting, we are able to provide a complete equational theory for language equivalence, with two notable features. First, the proposed axiomatisation is finite. Second, the Kleene star is a derived concept, as it can be decomposed into more primitive algebraic blocks.
- Subjects
EQUIVALENCE (Linguistics); FINITE, The; PHILOSOPHY of language; SYNTAX (Grammar)
- Publication
Logical Methods in Computer Science (LMCS), 2023, Vol 19, Issue 1, p1
- ISSN
1860-5974
- Publication type
Article
- DOI
10.46298/LMCS-19(113)2023