Dissemin is shutting down on January 1st, 2025

Published in

Springer Verlag, Lecture Notes in Computer Science, p. 247-259

DOI: 10.1007/978-3-319-62809-7_18

World Scientific Publishing, International Journal of Foundations of Computer Science, 01(30), p. 135-169, 2019

DOI: 10.1142/s0129054119400070

Links

Tools

Export citation

Search in Google Scholar

The Generalized Rank of Trace Languages

Journal article published in 2017 by Michal Kunc, Jan Meitner ORCID
This paper was not found in any repository, but could be made available legally by the author.
This paper was not found in any repository, but could be made available legally by the author.

Full text: Unavailable

Green circle
Preprint: archiving allowed
Green circle
Postprint: archiving allowed
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

Given a partially commutative alphabet and a set of words [Formula: see text], the rank of [Formula: see text] expresses the amount of shuffling required to produce a word belonging to [Formula: see text] from two words whose concatenation belongs to the closure of [Formula: see text] with respect to the partial commutation. In this paper, the notion of rank is generalized from concatenations of two words to an arbitrary fixed number of words. In this way, an infinite sequence of non-negative integers and infinity is assigned to every set of words. It is proved that in the case of alphabets defining free commutative monoids, as well as in the more general case of direct products of free monoids, sequences of ranks of regular sets are exactly non-decreasing sequences that are eventually constant. On the other hand, by uncovering a relationship between rank sequences of regular sets and rational series over the min-plus semiring, it is shown that already for alphabets defining free products of free commutative monoids, rank sequences need not be eventually periodic.