The generalized rank of trace languages

J 2019

The generalized rank of trace languages

KUNC, Michal a Jan MEITNER

Základní údaje

Originální název

The generalized rank of trace languages

Autoři

KUNC, Michal (203 Česká republika, garant, domácí) a Jan MEITNER (203 Česká republika, domácí)

Vydání

International Journal of Foundations of Computer Science, Singapore, World Scientific Publishing Co Pte Ltd, 2019, 0129-0541

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Singapur

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.523

Kód RIV

RIV/00216224:14310/19:00107334

Organizační jednotka

Přírodovědecká fakulta

DOI

http://dx.doi.org/10.1142/S0129054119400070

UT WoS

000460314500008

Klíčová slova anglicky

trace language; rank; regular language; rational series; tropical semiring

Štítky

rivok

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 17. 3. 2020 13:25, Mgr. Marie Šípková, DiS.

Anotace

V originále

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

GA15-02862S, projekt VaV

Název: Aplikace algebry a kombinatoriky v teorii formálních jazyků

Investor: Grantová agentura ČR, Aplikace algebry a kombinatoriky v teorii formálních jazyků

Citovat

KUNC, Michal a Jan MEITNER. The generalized rank of trace languages. International Journal of Foundations of Computer Science. Singapore: World Scientific Publishing Co Pte Ltd, 2019, roč. 30, č. 1, s. 135-169. ISSN 0129-0541. Dostupné z: https://dx.doi.org/10.1142/S0129054119400070.

@article{1513158,
   author = {Kunc, Michal and Meitner, Jan},
   article_location = {Singapore},
   article_number = {1},
   doi = {http://dx.doi.org/10.1142/S0129054119400070},
   keywords = {trace language; rank; regular language; rational series; tropical semiring},
   language = {eng},
   issn = {0129-0541},
   journal = {International Journal of Foundations of Computer Science},
   title = {The generalized rank of trace languages},
   url = {https://www.worldscientific.com/doi/10.1142/S0129054119400070},
   volume = {30},
   year = {2019}
}

TY  - JOUR
ID  - 1513158
AU  - Kunc, Michal - Meitner, Jan
PY  - 2019
TI  - The generalized rank of trace languages
JF  - International Journal of Foundations of Computer Science
VL  - 30
IS  - 1
SP  - 135-169
EP  - 135-169
PB  - World Scientific Publishing Co Pte Ltd
SN  - 01290541
KW  - trace language
KW  - rank
KW  - regular language
KW  - rational series
KW  - tropical semiring
UR  - https://www.worldscientific.com/doi/10.1142/S0129054119400070
L2  - https://www.worldscientific.com/doi/10.1142/S0129054119400070
N2  - 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.
ER  -

KUNC, Michal a Jan MEITNER. The generalized rank of trace languages. \textit{International Journal of Foundations of Computer Science}. Singapore: World Scientific Publishing Co Pte Ltd, 2019, roč.~30, č.~1, s.~135-169. ISSN~0129-0541. Dostupné z: https://dx.doi.org/10.1142/S0129054119400070.

Podrobný výpis o publikaci