Algorithmics of Posets Generated by Words Over Partially Commutative Alphabets (Extended)

Published in Volume XXIII, Issue 2, 2013, pages 229-249, doi: 10.7561/SACS.2013.2.229

Authors: Ł. Mikulski, M. Piątkowski, S. Smyczyński

Abstract

It is natural to try to relate partially ordered sets (posets in short) and classes of equivalent words over partially commutative alphabets. Their common graphical representation are Hasse diagrams. We investigate this relation in detail and propose an efficient online algorithm that decompresses a concurrent word to its Hasse diagram. The lexicographically minimal representative of an equivalence class of words is called the lexicographical normal form of this class. We give an algorithm which enumerates, in the lexicographical order, all distinct classes of words identified by their lexicographical normal forms. The two presented algorithms are the main contribution of this paper.

Full Text (PDF)

References

[1] G. Brightwell and P. Winkler. Counting linear extensions is #P-complete. In ACM Symposium on Theory of Computing (STOC), pages 175–181, 1991. http://dx.doi.org/10.1145/103418.103441

[2] O. Cogis and M. Habib. Nombre de sauts et graphes série- parallèles. RAIRO- Informatique théorique, 13(1):3–18, 1979.

[3] C.J. Colbourn and W.R. Pulleyblank. Minimizing setups in ordered sets of fixed width. Order, 1(3):225–229, 1985.. http://dx.doi.org/10.1007/BF00383598

[4] V. Diekert. Combinatorics on Traces, volume 454 of Lecture Notes in Computer Science. Springer, 1990. http://dx.doi.org/10.1007/3-540-53031-2

[5] V. Diekert and Y. Métivier. Partial commutation and traces, pages 457–533. Springer-Verlag New York, Inc., New York, NY, USA, 1997. http://dx.doi.org/10.1007/978-3-642-59126-6_8

[6] V. Diekert and G. Rozenberg (editors). The Book of Traces. World Scientific, Singapore, 1995.

[7] D.E. Knuth. The Art of Computer Programming, Volume 3. Addison-Wesley, Reading, 1973.

[8] D.E. Knuth. The Art of Computer Programming: Volume 4, Fascicle 3. Generating All Combinations and Partitions. Addison-Wesley, 2005.

[9] D. Kuske. Infinite series-parallel posets: Logic and languages. Lecture Notes in Computer Science, 1853:648–662, 2000. http://dx.doi.org/10.1007/3-540-45022-X_55

[10] A.B. Kwiatkowska and M. M. Sysło. On page number of N-free posets. Electronic Notes in Discrete Mathematics, 24:243 – 249, 2006. Fifth Cracow Conference on Graph Theory USTRON ’06. http://dx.doi.org/10.1016/j.endm.2006.06.030

[11] A. Mazurkiewicz. Concurrent program schemes and their interpretations. Daimi report PB-78, Aarhus University, 1977.

[12] Ł. Mikulski. Projection representation of Mazurkiewicz traces. Fundamenta Informaticae, 85:399–408, 2008.

[13] Ł. Mikulski, M. Piatkowski and S. Smyczynski. Algorithmics of posets generated by words over partially commutative alphabets. In Proceedings of the Prague Stringology Conference, Prague, Czech Republic, 2011, pages 209–219, 2011.

[14] K. Sayood. Introduction to Data Compression. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1996.

[15] M.M. Sysło. Minimizing the jump number for partially ordered sets: A graph-theoretic approach. Order, 1:7–19, 1984. http://dx.doi.org/10.1007/BF00396269 .

[16] K. Takamizawa, T. Nishizeki and N. Saito. Linear-time computability of combinatorial problems on series-parallel graphs. Journal of the ACM, 29(3):623–641, 1982. http://dx.doi.org/10.1145/322326.322328 .

[17] J. Valdes. Parsing Flowcharts and Series-Parallel Graphs. Ph.D. dissertation, Stanford University, Stanford, 1978.

[18] J. Valdes, R.E. Tarjan and E.L. Lawler. The recognition of series parallel digraphs. In ACM Symposium on Theory of Computing (STOC), pages 1–12, 1979. http://dx.doi.org/10.1145/800135.804393 .

Bibtex

@article{sacscuza:mikulski2013aopgbwopca(,
  title={Algorithmics of Posets Generated by Words Over Partially Commutative Alphabets (Extended)},
  author={{L}. Mikulski and M. Pik{a}tkowski and S. Smyczy'nski},
  journal={Scientific Annals of Computer Science},
  volume={23},
  number={2},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2013},
  pages={229--249},
  doi={10.7561/SACS.2013.2.229},
  publisher={``A.I. Cuza'' University Press}
}