Equational axioms associated with finite automata for fixed point operations in cartesian categories

DOI10.1017/S0960129515000031zbMATH Open1364.68267arXiv1501.02190OpenAlexW1970133423MaRDI QIDQ2973247FDOQ2973247

Authors: Zoltán Ésik 

Publication date: 3 April 2017

Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)

Abstract: The axioms of iteration theories, or iteration categories, capture the equational properties of fixed point operations in several computationally significant categories. Iteration categories may be axiomatized by the Conway identities and identities associated with finite automata. We show that in conjunction with the Conway identities, each identity associated with a finite automaton implies the identity associated with any input extension of the automaton. We conclude that the Conway identities and the identities associated with the members of a subclass $cQ$ of finite automata is complete for iteration categories iff for every finite simple group $G$ there is an automaton $$ such that $G$ is a quotient of a group in the monoid $$ of the automaton $$. We also prove a stronger result that concerns identities associated with finite automata with a distinguished initial state.

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

Recommendations

• Equational properties of fixed point operations in Cartesian categories: an overview
• Equational properties of fixed-point operations in Cartesian categories: an overview
• scientific article; zbMATH DE number 2150281
• scientific article; zbMATH DE number 46168
• scientific article; zbMATH DE number 1114042
• Equational properties of iteration in algebraically complete categories
• scientific article; zbMATH DE number 3319584
• A categorical approach to the theory of equations
• Equational theories for automata
• Publication:3028349

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70) Equational classes, universal algebra in model theory (03C05) Closed categories (closed monoidal and Cartesian closed categories, etc.) (18D15)

Cites Work

• Equational properties of iteration in algebraically complete categories
• Group axioms for iteration
• The equational logic of fixed points
• Completeness of Park induction
• Solutions of the Iteration Equation and Extensions of the Scalar Iteration Operation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• FUNCTORIAL SEMANTICS OF ALGEBRAIC THEORIES
• Axiomatizing iteration categories
• Title not available (Why is that?)
• Fixed-point operations on ccc's. I
• THE POWER OF THE GROUP-IDENTITIES FOR ITERATION

Cited In (3)

• Equational properties of fixed point operations in Cartesian categories: an overview
• Equational properties of stratified least fixed points (extended abstract)
• Equational properties of fixed-point operations in Cartesian categories: an overview

This page was built for publication: Equational axioms associated with finite automata for fixed point operations in cartesian categories

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