The generalized rank of trace languages
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14310%2F19%3A00107334" target="_blank" >RIV/00216224:14310/19:00107334 - isvavai.cz</a>
Result on the web
<a href="https://www.worldscientific.com/doi/10.1142/S0129054119400070" target="_blank" >https://www.worldscientific.com/doi/10.1142/S0129054119400070</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1142/S0129054119400070" target="_blank" >10.1142/S0129054119400070</a>
Alternative languages
Result language
angličtina
Original language name
The generalized rank of trace languages
Original language description
Given a partially commutative alphabet and a set of words L, the rank of L expresses the amount of shuffling required to produce a word belonging to L from two words whose concatenation belongs to the closure of L 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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
<a href="/en/project/GA15-02862S" target="_blank" >GA15-02862S: Applications of Algebra and Combinatorics in Formal Language Theory</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
International Journal of Foundations of Computer Science
ISSN
0129-0541
e-ISSN
1793-6373
Volume of the periodical
30
Issue of the periodical within the volume
1
Country of publishing house
SG - SINGAPORE
Number of pages
35
Pages from-to
135-169
UT code for WoS article
000460314500008
EID of the result in the Scopus database
2-s2.0-85062513658