On the homomorphism order of labeled posets. (English) Zbl 1231.06001
Summary: Partially ordered sets labeled with \(k\) labels (\(k\)-posets) and their homomorphisms are examined. We give a representation of directed graphs by \(k\)-posets; this provides a new proof of the universality of the homomorphism order of \(k\)-posets. This universal order is a distributive lattice. We investigate some other properties, namely the infinite distributivity, the computation of infinite suprema and infima, and the complexity of certain decision problems involving the homomorphism order of \(k\)-posets. Sublattices are also examined.
MSC:
| 06A06 | Partial orders, general |
| 05C20 | Directed graphs (digraphs), tournaments |
| 06D05 | Structure and representation theory of distributive lattices |
Keywords:
partial order; labeled poset; homomorphism; representation of directed graphs by \(k\)-posets; complexity of decision problemsReferences:
| [1] | Bloom, S.L., Ésik, Z.: Free shuffle algebras in language varieties. Theor. Comput. Sci. 163, 55–98 (1996) · Zbl 0874.68171 · doi:10.1016/0304-3975(95)00230-8 |
| [2] | Blyth, T.S.: Lattices and Ordered Algebraic Structures. Springer, London (2005) · Zbl 1073.06001 |
| [3] | Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order, 2nd edn. Cambridge University Press (2002) · Zbl 1002.06001 |
| [4] | Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations. Springer, Berlin, Heidelberg (1999) · Zbl 0909.06001 |
| [5] | Gischer, J.L.: The equational theory of pomsets. Theor. Comput. Sci. 61, 199–224 (1988) · Zbl 0669.68015 · doi:10.1016/0304-3975(88)90124-7 |
| [6] | Grabowski, J.: On partial languages. Ann. Soc. Math. Pol., Ser. IV Fund. Inform. 4(2), 427–498 (1981) · Zbl 0468.68088 |
| [7] | Grätzer, G.: General Lattice Theory, 2nd edn. Birkhäuser, Berlin (2003) · Zbl 1152.06300 |
| [8] | Hell, P., Nešetřil, J.: On the complexity of H-coloring. J. Comb. Theory, Ser. B 48, 92–110 (1990) · Zbl 0639.05023 · doi:10.1016/0095-8956(90)90132-J |
| [9] | Hell, P., Nešetřil, J.: The core of a graph. Discrete Math. 109, 117–126 (1992) · Zbl 0803.68080 · doi:10.1016/0012-365X(92)90282-K |
| [10] | Hell, P., Nešetřil, J.: Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and Its Applications, vol. 28. Oxford University Press, Oxford, New York (2004) |
| [11] | Hubička, J., Nešetřil, J.: Universal partial order represented by means of oriented trees and other simple graphs. Eur. J. Comb. 26, 765–778 (2005) · Zbl 1060.05092 · doi:10.1016/j.ejc.2004.01.008 |
| [12] | Kosub, S.: NP-partitions over posets with an application to reducing the set of solutions of NP problems. Theory Comput. Syst. 38, 83–113 (2005) · Zbl 1061.68076 · doi:10.1007/s00224-004-1114-1 |
| [13] | Kosub, S., Wagner, K.W.: The Boolean hierarchy of NP-partitions. In: Reichel, H., Tison, S. (eds.) STACS 2000, 17th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Comput. Sci., vol. 1770, pp. 157–168. Springer, Berlin (2000). An expanded version is available as Technical Report TUM-I0209. Institut für Informatik, Technische Universität München, München (2002) · Zbl 0959.68521 |
| [14] | Kudinov, O.V., Selivanov, V.L.: Undecidability in the homomorphic quasiorder of finite labeled forests. In: Beckmann, A., Berger, U., Löwe, B., Tucker, J.V. (eds.) Logical Approaches to Computational Barriers. Lecture Notes in Comput. Sci., vol. 3988, pp. 289–296. Springer, Berlin (2006) · Zbl 1145.03307 |
| [15] | Kuske, D.: Theories of orders on the set of words. RAIRO–Theor. Inf. Appl. 40, 53–74 (2006) · Zbl 1098.03021 · doi:10.1051/ita:2005039 |
| [16] | Lehtonen, E.: Descending chains and antichains of the unary, linear, and monotone subfunction relations. Order 23, 129–142 (2006) · Zbl 1124.08002 · doi:10.1007/s11083-006-9036-y |
| [17] | Lehtonen, E.: Labeled posets are universal. Eur. J. Comb. 29, 493–506 (2008) · Zbl 1133.06003 · doi:10.1016/j.ejc.2007.02.005 |
| [18] | MacNeille, H.M.: Partially ordered sets. Trans. Am. Math. Soc. 42, 416–460 (1937) · JFM 63.0833.04 · doi:10.1090/S0002-9947-1937-1501929-X |
| [19] | Nešetřil, J., Pultr, A., Tardif, C.: Gaps and dualities in Heyting categories. Comment. Math. Univ. Carol. 48, 9–23 (2007) · Zbl 1199.18009 |
| [20] | Pratt, V.R.: Modelling concurrency with partial orders. Int. J. Parallel Program. 15, 33–71 (1987) · Zbl 0622.68034 · doi:10.1007/BF01379149 |
| [21] | Pultr, A., Trnková, V.: Combinatorial, Algebraic and Topological Representations of Groups, Semigroups and Categories. North-Holland, Amsterdam (1980) · Zbl 0418.18004 |
| [22] | Rensink, A.: Algebra and theory of order-deterministic pomsets. Notre Dame J. Form. Log. 37, 283–320 (1996) · Zbl 0865.06004 · doi:10.1305/ndjfl/1040046090 |
| [23] | Selivanov, V.L.: Boolean hierarchies of partitions over a reducible base. Algebra Logic 43, 44–61 (2004). Translated from Algebra Logika 43, 77–109 (2004) · doi:10.1023/B:ALLO.0000015130.31054.b3 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
