| KUNC, Michal and 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, p. 247-259. ISBN 978-3-319-62808-0. Available from: https://dx.doi.org/10.1007/978-3-319-62809-7_18. |
Other formats:
BibTeX
LaTeX
RIS
@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 and 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, p.~247-259. ISBN~978-3-319-62808-0. Available from: https://dx.doi.org/10.1007/978-3-319-62809-7\_{}18.
|
