Free inductive K-semialgebras

DOI10.1016/J.JLAP.2013.01.001zbMATH Open1286.68332arXiv1009.4820OpenAlexW1748837224MaRDI QIDQ383784FDOQ383784

Zoltán Ésik, W. Kuich

Publication date: 6 December 2013

Published in: The Journal of Logic and Algebraic Programming (Search for Journal in Brave)

Abstract: We consider rational power series over an alphabet $Sigma$ with coefficients in a ordered commutative semiring $K$ and characterize them as the free ordered $K$-semialgebras in various classes of ordered $K$-semialgebras equipped with a star operation satisfying the least pre-fixed point rule and/or its dual. The results are generalizations of Kozen's axiomatization of regular languages.

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

zbMATH Keywords

complete axiomatizationfixed point inductioninductive semiringrational power series

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70) Ordered structures (06F99) Algebraic structures (08A99)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Group axioms for iteration
• Matrix and matricial iteration theories. I
• Axiomatizing rational power series over natural numbers
• Free iterative and iteration \(K\)-semialgebras
• Two Complete Axiom Systems for the Algebra of Regular Events
• Complete systems of \(\mathcal B\)-rational identities
• A completeness theorem for Kleene algebras and the algebra of regular events
• Une remarque sur les systèmes complets d'identités rationnelles
• Inductive \(^{*}\)-semirings
• Conjugacy and Equivalence of Weighted Automata and Functional Transducers
• Iteration Semirings
• A GENERALIZATION OF KOZEN'S AXIOMATIZATION OF THE EQUATIONAL THEORY OF THE REGULAR SETS
• Finite Automata
• Automata, Languages and Programming

Cited In (7)

• Equational properties of fixed-point operations in cartesian categories: An overview
• A connection between concurrency and language theory
• Free iterative and iteration \(K\)-semialgebras
• Equational Properties of Fixed Point Operations in Cartesian Categories: An Overview
• A generalized partition refinement algorithm, instantiated to language equivalence checking for weighted automata
• Equational theories for automata
• Canonical forms for free {\kappa}-semigroups

This page was built for publication: Free inductive \(K\)-semialgebras

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