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

DOI10.1017/S0960129515000031MaRDI QIDQ2973247zbMATH OpenOpenAlexFDO

Authors Zoltán Ésik

Publication date 3 April 2017

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3731311 (Why is no real title available?)
• scientific article; zbMATH DE number 3512082 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 233974 (Why is no real title available?)
• Axiomatizing iteration categories
• Completeness of Park induction
• Equational properties of iteration in algebraically complete categories
• FUNCTORIAL SEMANTICS OF ALGEBRAIC THEORIES
• Fixed-point operations on ccc's. I
• Group axioms for iteration
• Solutions of the Iteration Equation and Extensions of the Scalar Iteration Operation
• THE POWER OF THE GROUP-IDENTITIES FOR ITERATION
• The equational logic of fixed points

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)