The generalized rank of trace languages

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

The generalized rank of trace languages

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

The generalized rank of trace languages

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GA15-02862S" target="_blank" >GA15-02862S: Aplikace algebry a kombinatoriky v teorii formálních jazyků</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

International Journal of Foundations of Computer Science

ISSN

0129-0541

e-ISSN

1793-6373

Svazek periodika

30

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

SG - Singapurská republika

Počet stran výsledku

35

Strana od-do

135-169

Kód UT WoS článku

000460314500008

EID výsledku v databázi Scopus

2-s2.0-85062513658