A Kleene-Schützenberger theorem for trace series over bounded lattices

MaRDI QIDQ2882389zbMATH OpenFDO

Authors Martin Huschenbett

Publication date 4 May 2012

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL http://iospress.metapress.com/content/y01p7x314587550p/fulltext.html

zbMATH Keywords

bimonoidsconcurrencyformal power seriesrational seriesrecognizable seriestrace languagesweighted automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

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.

Recommendations

• A Kleene-Schützenberger theorem for Lindenmayerian rational power series
• scientific article; zbMATH DE number 1501607
• An extension of Kleene's and Ochmański's theorems to infinite traces
• A sharp upper bound for the size of Lusztig series
• The Kleene-Schützenberger theorem for formal power series in partially commuting variables.
• Schur's theorem in integer lattices
• The density theorem for discrete series representations restricted to lattices
• A fixed point theorem with applications to truncated lattices
• \(l\)-trace \(k\)-Sperner families of sets
• Cantor-Bernstein theorem for lattices

Cited in

(1)

• Schützenberger's theorem on formal power series follows from Kleene's theorem

This page was built for publication: A Kleene-Schützenberger theorem for trace series over bounded lattices

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