The generalized rank of trace languages

Autoři

KUNC Michal MEITNER Jan

Druh Článek ve sborníku
Konference Developments in Language Theory. 21st International Conference, DLT 2017, Liege, Belgium, August 7-11, 2017, Proceedings
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
Doi http://dx.doi.org/10.1007/978-3-319-62809-7_18
Obor Obecná matematika
Klíčová slova Trace language; Rank; Regular language; Rational series; Tropical semiring
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.