A Kleene-Schützenberger theorem for trace series over bounded lattices
type: Item
instance of: scholarly article
zbMATH Open document ID: 1257.68097
author: Martin Huschenbett
publication date: 2012-05-04T00:00:00Z
full work available at URL: fulltext.html
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 68Q85
zbMATH DE Number: 6030477
zbMATH Keywords: trace languages
zbMATH Keywords: formal power series
zbMATH Keywords: weighted automata
zbMATH Keywords: recognizable series
zbMATH Keywords: rational series
zbMATH Keywords: bimonoids
zbMATH Keywords: concurrency
MaRDI profile type: Publication
Recommended article: A Kleene-Schützenberger theorem for Lindenmayerian rational power series
Recommended article: Q4500367
Recommended article: An extension of Kleene's and Ochmański's theorems to infinite traces
Recommended article: A sharp upper bound for the size of Lusztig series
Recommended article: The Kleene-Schützenberger theorem for formal power series in partially commuting variables.
Recommended article: Schur's theorem in integer lattices
Recommended article: The density theorem for discrete series representations restricted to lattices
Recommended article: A fixed point theorem with applications to truncated lattices
Recommended article: \(l\)-trace \(k\)-Sperner families of sets
Recommended article: Cantor-Bernstein theorem for lattices
title: A Kleene-Schützenberger theorem for trace series over bounded lattices
published in: Fundamenta Informaticae
review text: The author investigates the relation between the recognizability and the rationality of weighted trace languages with weights in a bimonoid, i.e., an algebra with two monoid structures. The bimonoids considered here have various additional properties like local finiteness, commutativity or idempotence. The two special types of rationality studied, \(c\)-rationality and \(mc\)-rationality, are defined by restricting the use of the iteration operation.NEWLINENEWLINE The main theorem states that a trace series over a bi-locally finite strong bimonoid is recognizable if and only if it is \(mc\)-rational, and that, if the bimonoid is also idempotent and commutative, then \(c\)-rationality implies recognizability. In particular, for trace series over a bounded lattice, recognizability, \(mc\)-rationality and \(c\)-rationality are equivalent properties.
reviewed by: Magnus Steinby
description: scientific article; zbMATH DE number 6030477