The generalized rank of trace languages

D 2017

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í

Cham, Švýcarsko, Developments in Language Theory. 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings, od s. 247-259, 13 s. 2017

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10101 Pure mathematics

Stát vydavatele

Švýcarsko

Utajení

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

Forma vydání

tištěná verze "print"

Odkazy

URL

Kód RIV

RIV/00216224:14310/17:00095162

Organizační jednotka

Přírodovědecká fakulta

ISBN

978-3-319-62808-0

DOI

http://dx.doi.org/10.1007/978-3-319-62809-7_18

UT WoS

000442555100024

Klíčová slova anglicky

Trace language; Rank; Regular language; Rational series; Tropical semiring

Štítky

NZ, rivok

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 23. 4. 2020 13:54, Mgr. Marie Šípková, DiS.

Anotace

V originále

The notion of rank of a language with respect to an independence alphabet is generalized from concatenations of two words to an arbitrary fixed number of words. It is proved that in the case of free commutative monoids, as well as in the more general case of direct products of free monoids, sequences of ranks of regular languages are exactly non-decreasing sequences that are eventually constant. On the other hand, by uncovering a relationship between rank sequences of regular languages and rational series over the min-plus semiring, it is shown that already for 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. In Émilie Charlier, Julien Leroy, Michel Rigo. Developments in Language Theory. 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings. Cham, Švýcarsko: Springer, 2017, s. 247-259. ISBN 978-3-319-62808-0. Dostupné z: https://dx.doi.org/10.1007/978-3-319-62809-7_18.

@inproceedings{1395129,
   author = {Kunc, Michal and Meitner, Jan},
   address = {Cham, Švýcarsko},
   booktitle = {Developments in Language Theory. 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings},
   doi = {http://dx.doi.org/10.1007/978-3-319-62809-7_18},
   editor = {Émilie Charlier, Julien Leroy, Michel Rigo},
   keywords = {Trace language; Rank; Regular language; Rational series; Tropical semiring},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Cham, Švýcarsko},
   isbn = {978-3-319-62808-0},
   pages = {247-259},
   publisher = {Springer},
   title = {The generalized rank of trace languages},
   url = {http://dx.doi.org/10.1007/978-3-319-62809-7_18},
   year = {2017}
}

TY  - JOUR
ID  - 1395129
AU  - Kunc, Michal - Meitner, Jan
PY  - 2017
TI  - The generalized rank of trace languages
PB  - Springer
CY  - Cham, Švýcarsko
SN  - 9783319628080
KW  - Trace language
KW  - Rank
KW  - Regular language
KW  - Rational series
KW  - Tropical semiring
UR  - http://dx.doi.org/10.1007/978-3-319-62809-7_18
L2  - http://dx.doi.org/10.1007/978-3-319-62809-7_18
N2  - The notion of rank of a language with respect to an independence alphabet is generalized from concatenations of two words to an arbitrary fixed number of words. It is proved that in the case of free commutative monoids, as well as in the more general case of direct products of free monoids, sequences of ranks of regular languages are exactly non-decreasing sequences that are eventually constant. On the other hand, by uncovering a relationship between rank sequences of regular languages and rational series over the min-plus semiring, it is shown that already for 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. In Émilie Charlier, Julien Leroy, Michel Rigo. \textit{Developments in Language Theory. 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings}. Cham, Švýcarsko: Springer, 2017, s.~247-259. ISBN~978-3-319-62808-0. Dostupné z: https://dx.doi.org/10.1007/978-3-319-62809-7\_{}18.

Podrobný výpis o publikaci