Injective envelopes of transition systems and Ferrers languages

Kabil, Mustapha; Pouzet, Maurice

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 54 (2020), article no. 4.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

We consider reflexive and involutive transition systems over an ordered alphabet A equipped with an involution. We give a description of the injective envelope of any two-element set in terms of Galois lattice, from which we derive a test of its finiteness. Our description leads to the notion of Ferrers language.

Classification : 06A15, 06D20, 46B85, 68Q70, 68R15
Mots-clés : Metric spaces, injective envelopes, transition systems, Ferrers languages, ordered sets, interval orders, well-quasi-order

[1] N. Aronszajn and P. Panitchpakdi, Extensions of uniformly continuous transformations and hyperconvex metric spaces. Pac. J. Math. 6 (1956) 405–439. | DOI | MR | Zbl

[2] B. Banaschewski and G. Bruns, Categorical characterization of the MacNeille completion. Arch. Math. Basel 18 (1967) 369–377. | DOI | MR | Zbl

[3] L. M. Blumenthal, Boolean geometry. Rend. Circ. Mat. Palermo 2 (1952) 343–360. | MR | Zbl

[4] L. M. Blumenthal, Theory and Applications of Distance Geometry, 2nd edn. Chelsea Publishing Co., New York (1970) xi+347. | MR | Zbl

[5] L. M. Blumenthal and K. Menger, Studies in Geometry, W. H. Freeman and Co., San Francisco, California (1970) xiv+512. | MR | Zbl

[6] A. Bouchet, Codages et Dimensions de Relations Binaires, Orders: Description and Roles. In Vol. 23 of Annals of Discrete Mathematics. Edited by M. Pouzet and D. Richard. Elsevier Amsterdam, The Netherlands (1984) 387–396. | MR | Zbl

[7] O. Cogis, On the Ferrers dimension of a digraph. Discrete Math. 38 (1982) 47–52. | DOI | MR | Zbl

[8] E. Corominas, Sur les ensembles ordonnés projectifs et la propriété du points fixe. C. R. Acad. Sci. Paris, Série A311 (1990) 199–204. | MR | Zbl

[9] B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, 2nd edn. Cambridge University Press, New York (2002) xii+298. | MR | Zbl

[10] M. Deza, E. Deza, Encyclopedia of Distances, 4th edn. Springer, Berlin (2016) xxii+756. | MR | Zbl

[11] J. P. Doignon, A. Ducamp, J. C. Falmagne, On realizable biorders and the biorder dimension of a relation. J. Math. Psych. 28 (1984) 73–109. | DOI | MR | Zbl

[12] A. W. N. Dress, Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups, a note on combinatorial properties of metric spaces. Adv. Math. 53 (1984) 321–402. | DOI | MR | Zbl

[13] A. W. N. Dress, Towards a classification of transitive group actions on finite metric spaces. Adv. Math. 74 (1989) 163–189. | DOI | MR | Zbl

[14] D. Duffus, I. Rival, A structure theory of ordered sets. J. Discrete Math. 35 (1981) 53–118. | DOI | MR | Zbl

[15] A. Ehrenfeucht, D. Haussler and G. Rozenberg, On regularity of context-free languages. Theor. Comput. Sci. 27 (1983) 311–332. | DOI | MR | Zbl

[16] P. Eklund, J. Gutiérrez García, U. Höhle and J. Kortelainen, Semigroups in Complete Lattices: Quantales, Modules and Related Topics, Developments in Mathematics. Springer, Berlin (2018). | DOI | MR

[17] R. Espínola and M. A. Khamsi, Introduction to Hyperconvex Spaces, in Handbook of Metric Fixed Point Theory. Kluwer Academic Publisher, Dordrecht (2001) 391–435. | MR | Zbl

[18] P. C. Fishburn, Interval Orders and Interval Graphs. Wiley Hoboken, NJ, USA (1985). | MR | Zbl

[19] G. Higman, Ordering by divisbility in abstract algebra. Proc. London Math. Soc. 3 (1952) 326–336. | DOI | MR | Zbl

[20] A. Hudry, Rétractions, corétractions et envelope injective d’une algèbre de transitions. Discrete Math. 247 (2002) 117–134. | DOI | MR | Zbl

[21] A. Hudry, Injective envelope and parallel decomposition of a transition system. Discrete Math. 289 (2004) 45–61. | DOI | MR | Zbl

[22] J. R. Isbell, Six theorems about injective metric spaces. Comment. Math. Helv. 39 (1964) 65–76. | DOI | MR | Zbl

[23] E. Jawhari, D. Misane and M. Pouzet, Retracts graphs and ordered sets from the metric point of view. Contemp. Math. 57 (1986) 175–226. | DOI | MR | Zbl

[24] P. Jullien, Sur un théorème d’extension dans la théorie des mots. C. R. Acad. Sci. Paris Série 266 (1968) 851–854. | MR | Zbl

[25] K. Kaarli and S. Radeleczki, Representation of integral quantales by tolerances. Algebra Universalis 79 (2018) 5. | DOI | MR | Zbl

[26] M. Kabil, M. Pouzet, Une extension d’un théorème de P. Jullien sur les âges de mots. RAIRO: ITA 26 (1992) 449–482. | Numdam | MR | Zbl

[27] M. Kabil and M. Pouzet, Indécomposabilité et irréductibilité dans la variété des rétractes absolus des graphes réflexifs. C. R. Acad. Sci. Paris Série A 321 (1995) 499–504. | MR | Zbl

[28] M. Kabil, Une approche métrique de l’indécomposabilité et de l’irréductibilité dans la variété des rétractes absolus des graphes et des systèmes de transitions. Thèse de doctorat d’État, Université Hassan II Aïn Chock, Casablanca, Morocco, 19 Décembre (1996).

[29] M. Kabil and M. Pouzet, Injective envelope of graphs and transition systems. Discrete Math. 192 (1998) 145–186. | DOI | MR | Zbl

[30] M. Kabil, M. Pouzet and I. G. Rosenberg, Free monoids and metric spaces. Euro. J. Combinatorics 80 (2019) 339–360. | DOI | MR | Zbl

[31] M. Kabil and M. Pouzet, Geometric Aspects of Generalized Metric Spaces: Relations with Graphs, Ordered Sets and Automata, Chap.11, in New Trends in Analysis and Geometry, edited by A. H Alkhaldi, M. K. Alaoui and M. A. Khamsi. Cambridge Scholars Publishing, Cambridge (2020) 319–377.

[32] A. D. Korshunov, The number of monotonic Boolean functions. Problemy Kibern 38 (1981) 5–108. | MR | Zbl

[33] M. Lothaire, Combinatorics on Words, Encyclopedia Mathematics Applied, Addison-Wesley, Boston, USA (1983) 17. | MR | Zbl

[34] K. Menger, Probabilistic geometry. Proc. Natl. Acad. Sci. USA 37 (1951) 226–229. | DOI | MR | Zbl

[35] M. Nivat, Personnalcommunication (1989).

[36] R. Nowakowski and I. Rival, The smallest graph variety containing all paths. J. Discrete Math. 43 (1983) 185–198. | MR | Zbl

[37] M. Pouzet, Une Approche Métrique de la Rétraction dans les Ensembles Ordonnés et les graphes, (French) [A Metric Approach to Retraction in Ordered Sets and Graphs] Proceedings of the conference on infinitistic mathematics (Lyon, 1984), 59–89, Publ. Dép. Math. Nouvelle Sér. B, 85-2, Univ. Claude-Bernard, Lyon (1985). | Numdam | MR | Zbl

[38] M. Pouzet and I. G. Rosenberg, General metrics and contracting operations. Discrete Math. 130 (1994) 103–169. | MR | Zbl

[39] M. Pouzet, When is the orbit algebra of a group an integral domain? Proof of a conjecture of P. J. Cameron. Theor. Inform. Appl. 42 (2008) 83–103. | DOI | Numdam | MR | Zbl

[40] M. Pouzet and H. Si Kaddour, N. Zaguia, Finite dimensional scattered posets. Euro. J. Combinatorics 37 (2014) 79–99. | DOI | MR | Zbl

[41] J. Riguet, Les relations de Ferrers. C. R. Acad. Sci. Paris Série A 232 (1951) 1729–1730. | MR | Zbl

[42] F. Saïdane, Graphe et languages: une approche metrique. Thèse de doctorat, Université Claude-Bernard, Lyon, France (1991).

[43] J. Sakarovitch, Elements of Automata Theory, Translated from the 2003 French original by Reuben Thomas. Cambridge University Press, Cambridge (2009). | MR | Zbl

[44] I. Simon, Piecewise Testable Events, Automata Theory and Formal Languages (Second GI Conf., Kaiserslautern, 1975), In Vol. 33 of Lecture Notes in Comput. Sciences. Springer, Berlin (1975) 214–222. | MR | Zbl

[45] J. Stern, Characterizations of some classes of regular events. Theor. Comput. Sci. 35 (1985) 17–42. | DOI | MR | Zbl

[46] G. Viennot, Factorisations des Monoïdes. Thèse de 3^ème cycle, Paris, Janvier (1971).

[47] D. Wiedemann, A computation of the eight Dedekind number. Order 8 (1991) 5–6. | DOI | MR | Zbl

[48] N. Wiener, A contribution to the theory of relative position. Proc. Camb. Philos. Soc. 17 (1914) 441–449. | JFM