A Kleene-Schützenberger theorem for trace series over bounded lattices (Q2882389)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A Kleene-Schützenberger theorem for trace series over bounded lattices |
scientific article; zbMATH DE number 6030477
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A Kleene-Schützenberger theorem for trace series over bounded lattices |
scientific article; zbMATH DE number 6030477 |
Statements
4 May 2012
0 references
trace languages
0 references
formal power series
0 references
weighted automata
0 references
recognizable series
0 references
rational series
0 references
bimonoids
0 references
concurrency
0 references
0.8986127
0 references
0.8675886
0 references
0.86210316
0 references
0.8593135
0 references
0 references
0.85785353
0 references
0.85614073
0 references
0.85396796
0 references
0 references
A Kleene-Schützenberger theorem for trace series over bounded lattices (English)
0 references
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.
0 references
