0000000000379866

AUTHOR

Giovanna Guaiana

showing 3 related works from this author

Coding with traces

1994

We prove that the existence of a coding between two trace monoids is decidable for some families of trace monoids. Decidability heavily depends on the structure of the dependence graphs. The concept of coding is based on the new notion of strong morphism between trace monoids.

CombinatoricsMorphismlawMathematics::Category TheorySuffix treeCoding (social sciences)MathematicsDecidabilitylaw.invention
researchProduct

On aperiodic trace languages

2005

Trace (semiology)Computer scienceAperiodic graphPrincipal idealMineralogy
researchProduct

Star-free trace languages

1992

Abstract Generalizing a classical result of Schutzenberger to free partially commutative monoids, we prove that the family of star-free trace languages coincides with the family of aperiodic trace languages.

MonoidPure mathematicsGeneral Computer ScienceAbstract family of languagesComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Star (graph theory)Cone (formal languages)Theoretical Computer ScienceTrace (semiology)Aperiodic graphFormal languageComputer Science::Programming LanguagesCommutative propertyMathematicsComputer Science(all)Theoretical Computer Science
researchProduct