Injective envelopes of transition systems and Ferrers languages. (English) Zbl 1481.06022

Summary: 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.


06A15 Galois correspondences, closure operators (in relation to ordered sets)
06D20 Heyting algebras (lattice-theoretic aspects)
54E35 Metric spaces, metrizability
46B85 Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science
68Q70 Algebraic theory of languages and automata
Full Text: DOI arXiv


[1] N. Aronszajn and P. Panitchpakdi, Extensions of uniformly continuous transformations and hyperconvex metric spaces. Pac. J. Math. 6 (1956) 405-439. · Zbl 0074.17802
[2] B. Banaschewski and G. Bruns, Categorical characterization of the MacNeille completion. Arch. Math. Basel 18 (1967) 369-377. · Zbl 0157.34101
[3] L.M. Blumenthal, Boolean geometry. Rend. Circ. Mat. Palermo 2 (1952) 343-360.
[4] L.M. Blumenthal, Theory and Applications of Distance Geometry, 2nd edn. Chelsea Publishing Co., New York (1970) xi+347.
[5] L.M. Blumenthal and K. Menger, Studies in Geometry, W. H. Freeman and Co., San Francisco, California (1970) xiv+512. · Zbl 0204.53401
[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.
[7] O. Cogis, On the Ferrers dimension of a digraph. Discrete Math. 38 (1982) 47-52. · Zbl 0472.06007
[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. · Zbl 0731.06001
[9] B.A. Davey and H.A. Priestley, Introduction to Lattices and Order, 2nd edn. Cambridge University Press, New York (2002) xii+298. · Zbl 1002.06001
[10] M. Deza, E. Deza, Encyclopedia of Distances, 4th edn. Springer, Berlin (2016) xxii+756. · Zbl 1351.51001
[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. · Zbl 0562.92018
[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. · Zbl 0562.54041
[13] A.W.N. Dress, Towards a classification of transitive group actions on finite metric spaces. Adv. Math. 74 (1989) 163-189. · Zbl 0683.54041
[14] D. Duffus, I. Rival, A structure theory of ordered sets. J. Discrete Math. 35 (1981) 53-118. · Zbl 0459.06002
[15] A. Ehrenfeucht, D. Haussler and G. Rozenberg, On regularity of context-free languages. Theor. Comput. Sci. 27 (1983) 311-332. · Zbl 0553.68044
[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). · Zbl 06863918
[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. · Zbl 1029.47002
[18] P.C. Fishburn, Interval Orders and Interval Graphs. Wiley Hoboken, NJ, USA (1985). · Zbl 0568.05047
[19] G. Higman, Ordering by divisbility in abstract algebra. Proc. London Math. Soc. 3 (1952) 326-336. · Zbl 0047.03402
[20] A. Hudry, Rétractions, corétractions et envelope injective d’une algèbre de transitions. Discrete Math. 247 (2002) 117-134. · Zbl 1013.08007
[21] A. Hudry, Injective envelope and parallel decomposition of a transition system. Discrete Math. 289 (2004) 45-61. · Zbl 1090.18002
[22] J.R. Isbell, Six theorems about injective metric spaces. Comment. Math. Helv. 39 (1964) 65-76. · Zbl 0151.30205
[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. · Zbl 0597.54028
[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. · Zbl 0157.03104
[25] K. Kaarli and S. Radeleczki, Representation of integral quantales by tolerances. Algebra Universalis 79 (2018) 5. · Zbl 1471.06009
[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. · Zbl 0754.68067
[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. · Zbl 0837.05096
[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. · Zbl 0955.05105
[30] M. Kabil, M. Pouzet and I.G. Rosenberg, Free monoids and metric spaces. Euro. J. Combinatorics 80 (2019) 339-360. · Zbl 07078541
[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. · Zbl 0521.94018
[33] M. Lothaire, Combinatorics on Words, Encyclopedia Mathematics Applied, Addison-Wesley, Boston, USA (1983) 17. · Zbl 0514.20045
[34] K. Menger, Probabilistic geometry. Proc. Natl. Acad. Sci. USA 37 (1951) 226-229. · Zbl 0042.37201
[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. · Zbl 0511.05059
[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).
[38] M. Pouzet and I.G. Rosenberg, General metrics and contracting operations. Discrete Math. 130 (1994) 103-169. · Zbl 0813.06010
[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. · Zbl 1146.03015
[40] M. Pouzet and H. Si Kaddour, N. Zaguia, Finite dimensional scattered posets. Euro. J. Combinatorics 37 (2014) 79-99. · Zbl 1346.06001
[41] J. Riguet, Les relations de Ferrers. C. R. Acad. Sci. Paris Série A 232 (1951) 1729-1730. · Zbl 0042.24317
[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). · Zbl 1188.68177
[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.
[45] J. Stern, Characterizations of some classes of regular events. Theor. Comput. Sci. 35 (1985) 17-42. · Zbl 0604.68066
[46] G. Viennot, Factorisations des Monoïdes. Thèse de \(3^{}\) ème cycle, Paris, Janvier (1971). · Zbl 0355.20059
[47] D. Wiedemann, A computation of the eight Dedekind number. Order 8 (1991) 5-6. · Zbl 0736.06017
[48] N. Wiener, A contribution to the theory of relative position. Proc. Camb. Philos. Soc. 17 (1914) 441-449. · JFM 45.1150.10
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.