On Aperiodic and Star-Free Formal Power Series in Partially Commuting Variables

Formal power series over non-commuting variables have been investigated as representations of the behavior of automata with multiplicities. Here we introduce and investigate the concepts of aperiodic and of star-free formal power series over semirings and partially commuting variables. We prove that...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2008-05, Vol.42 (4), p.608-631
Main Authors: Droste, Manfred, Gastin, Paul
Format: Article
Language:English
Subjects:
Automation
Boolean
Committees
Commuting
Computer programming
Computer Science
Investigations
Operations research
Optimization
Programming languages
Studies
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Formal power series over non-commuting variables have been investigated as representations of the behavior of automata with multiplicities. Here we introduce and investigate the concepts of aperiodic and of star-free formal power series over semirings and partially commuting variables. We prove that if the semiring K is idempotent and commutative, or if K is idempotent and the variables are non-commuting, then the product of any two aperiodic series is again aperiodic. We also show that if K is idempotent and the matrix monoids over K have a Burnside property (satisfied, e.g. by the tropical semiring), then the aperiodic and the star-free series coincide. This generalizes a classical result of Schützenberger (Inf. Control 4:245–270, 1961 ) for aperiodic regular languages and subsumes a result of Guaiana et al. (Theor. Comput. Sci. 97:301–311, 1992 ) on aperiodic trace languages.
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-007-9064-z