Transposition Rearrangement in Weighted Length Cost Model

• Autorzy: Łukasz Mikulski

Warianty tytułu

Reorganizacja przez transpozycje w ważonym modelu kosztu opartym na odległości

• Języki publikacji: EN

Abstrakty

EN

We extend the simplest case of the classical Length Cost Model of rearranging strings by transpositions to the Weighted Length Cost Model. We solve the problem of computing the cost of rearrangement in binary alphabet case, giving an online, constant space and linear algorithm. Then we extend this algorithm to solve the general case. The resulting solution has also the linear time complexity. At the end, we give some basic applications of the model in the Trace Theory and analysis of modelled with traces concurrent systems. (original abstract)

Rozszerzony został najprostszy przypadek klasycznego modelu Length Cost Model reorganizacji napisów przez transpozycje do modelu Weighted Length Cost Model. Rozwiązano problem obliczania kosztu reorganizacji w przypadku alfabetu binarnego, dając liniowy algorytm on-line działający w stałej pamięci. Algorytm ten został rozszerzony na przypadek ogólny, bez utraty liniowej złożoności czasowej. Na koniec podano proste aplikacje przedstawionego modelu w teorii śladów Mazurkiewicza i analizie systemów współbieżnych modelowanych przy pomocy śladów. (abstrakt oryginalny)

Słowa kluczowe

EN

Algorithms; Cost models; Linear models

PL

Algorytmy; Modele kosztów; Modele liniowe

• Czasopismo: Studia i Materiały Polskiego Stowarzyszenia Zarządzania Wiedzą
• Rocznik: 2011
• Tom: 42
• Strony: 115--125

Twórcy

autor

Łukasz Mikulski

• Nicolaus Copernicus University in Toruń, Poland

Bibliografia

• [1] Cayley A., Note on the theory of permutations, Philosophical Magazine 34, Taylor & Francis, London 1849: p. 527-529.
• [2] Diekert V., Metivier Y., Partial commutations and traces, [in:] Rozenberg G., Salomaa A. (eds.) Handbook of Formal Languages, volume III, Springer, Berlin-Heidelberg 2003: p. 457-534.
• [3] Gusfield D., Algorithms on Strings,Trees and Sequences: Computer Science and Computational Biology, Cambridge University Press, Cambridge 1999.
• [4] Kapah O. et al., Interchange Rearrangement: The Element-Cost Model, [in:] String Processing and Information Retrieval, LNCS 5280, Springer, Berlin-Heidelberg 2008: p. 224-235.
• [5] Mazurkiewicz A., Concurrent program schemes and their interpretations, DAIMI Report PB-78, Aarhus University, Aarhus 1977.
• [6] Mikulski Ł., Projection representation of Mazurkiewicz traces, Fundamenta Informaticae 85, IOS Press, Amsterdam 2008: p. 399-408.