Další formáty:
BibTeX
LaTeX
RIS
@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.
|