pith. sign in

arxiv: 1907.02231 · v1 · pith:WH537UOSnew · submitted 2019-07-04 · 🧮 math.CO · cs.IT· math.IT

Injective envelopes of transition systems and Ferrers languages

Mustapha Kabil , Maurice Pouzet This is my paper

Pith reviewed 2026-05-25 09:34 UTC · model grok-4.3

classification 🧮 math.CO cs.ITmath.IT
keywords injective envelopetransition systemsGalois latticeFerrers languagefiniteness testordered alphabetinvolution
0
0 comments X

The pith

The injective envelope of any two-element set in reflexive involutive transition systems is described by a Galois lattice, yielding a finiteness test and the notion of Ferrers language.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines reflexive and involutive transition systems over an ordered alphabet equipped with an involution. It provides a description of the injective envelope of any two-element set using the Galois lattice. This description yields a test for whether the envelope is finite and introduces Ferrers languages as a new concept arising from the construction. A reader would care because the work links transition system structure directly to lattice-theoretic objects and supplies a concrete criterion for finiteness in this setting.

Core claim

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.

What carries the argument

Galois lattice of the two-element set, which describes its injective envelope.

Load-bearing premise

The transition systems under consideration are reflexive and involutive over an ordered alphabet A equipped with an involution.

What would settle it

A reflexive involutive transition system on an ordered alphabet with involution in which the injective envelope of some two-element set fails to match the corresponding Galois lattice.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript considers reflexive and involutive transition systems over an ordered alphabet A equipped with an involution. It claims to give an explicit description of the injective envelope of any two-element set in terms of a Galois lattice, derives a finiteness test from this description, and introduces the notion of Ferrers languages as a consequence.

Significance. If the Galois-lattice construction holds, the result supplies a concrete, direct description of injective envelopes for two-element sets rather than a reduction to fitted parameters, together with an immediately derivable finiteness criterion. This could be useful in order-theoretic automata theory and may open avenues for classifying languages via the new Ferrers-language notion. The manuscript ships an explicit construction under the stated hypotheses.

major comments (2)
  1. [Main theorem / section deriving the finiteness test] The central claim is the Galois-lattice description of the injective envelope together with the derived finiteness test. The manuscript states the hypotheses (reflexive and involutive transition systems) clearly in the opening, but the passage from the lattice construction to the explicit finiteness criterion is presented without an intermediate lemma isolating the decidable condition on the lattice; this step is load-bearing for the test and requires a numbered statement.
  2. [Definition of Ferrers language] The definition of Ferrers language is introduced as a direct outgrowth of the envelope description. It is not compared with existing notions of Ferrers relations or diagrams in the literature; if the novelty rests on this definition, a precise statement of how it differs from prior uses of the term is needed to support the claim that the description 'leads to' a new notion.
minor comments (2)
  1. [Abstract] The abstract asserts the existence of the description and test but supplies no derivation outline or small example; adding one sentence summarizing the lattice construction would improve readability without lengthening the abstract.
  2. [Preliminaries / notation] Notation for the involution on A and the transition relation should be fixed once at the beginning and used uniformly; occasional re-use of symbols for different objects appears in the preliminary sections.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive suggestions. We address the two major comments below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Main theorem / section deriving the finiteness test] The central claim is the Galois-lattice description of the injective envelope together with the derived finiteness test. The manuscript states the hypotheses (reflexive and involutive transition systems) clearly in the opening, but the passage from the lattice construction to the explicit finiteness criterion is presented without an intermediate lemma isolating the decidable condition on the lattice; this step is load-bearing for the test and requires a numbered statement.

    Authors: We agree that the transition from the Galois-lattice construction to the finiteness criterion would benefit from an explicit intermediate statement. We will add a numbered lemma that isolates the decidable condition on the lattice. revision: yes

  2. Referee: [Definition of Ferrers language] The definition of Ferrers language is introduced as a direct outgrowth of the envelope description. It is not compared with existing notions of Ferrers relations or diagrams in the literature; if the novelty rests on this definition, a precise statement of how it differs from prior uses of the term is needed to support the claim that the description 'leads to' a new notion.

    Authors: The Ferrers-language notion is introduced here as a direct consequence of the envelope construction in the setting of reflexive involutive transition systems. To clarify its status, we will insert a short remark distinguishing the new definition from classical Ferrers relations in order theory. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained mathematical description

full rationale

The paper states its central result as a direct Galois-lattice description of the injective envelope of any two-element set for reflexive involutive transition systems on an ordered alphabet with involution, from which a finiteness test is derived and the notion of Ferrers language is introduced. No equations, fitted parameters, predictions of related quantities, or self-citations appear in the provided abstract or claim summary. The construction is presented as an explicit description under explicitly stated hypotheses rather than a reduction to prior fitted inputs or self-referential definitions. No load-bearing step reduces by construction to the inputs; the result is independent of any internal fitting or renaming.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on the standard mathematical properties of Galois lattices and the definition of reflexive involutive transition systems; no free parameters or invented entities beyond the new language class are visible in the abstract.

axioms (2)
  • domain assumption Galois lattices exist and can represent the injective envelope of two-element sets in the given transition systems
    Invoked by the claim that the envelope is described in terms of a Galois lattice.
  • domain assumption The alphabet is ordered and equipped with an involution
    Stated as the setting for the transition systems considered.
invented entities (1)
  • Ferrers language no independent evidence
    purpose: New class of languages obtained from the Galois-lattice description of the injective envelope
    Introduced by the paper as a direct consequence of the description

pith-pipeline@v0.9.0 · 5564 in / 1319 out tokens · 26366 ms · 2026-05-25T09:34:28.016150+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages · 1 internal anchor

  1. [1]

    Banaschewski, G

    B. Banaschewski, G. Bruns, Categorical characterization of the MacNeille completion, Arch. Math. (Basel) 18 (1967) 369–377

    work page 1967

  2. [2]

    Bouchet, Codages et dimensions de relations binaires , Annals of discrete Mathematics 23, Orders: Description and roles, (M

    A. Bouchet, Codages et dimensions de relations binaires , Annals of discrete Mathematics 23, Orders: Description and roles, (M. Pouzet,D. Richard Eds), 387-396. 1984. 22 M.KABIL AND M. POUZET

    work page 1984

  3. [3]

    Blumenthal, Boolean geometry, I

    L.M. Blumenthal, Boolean geometry, I. Rend. Circ. Mat. Palermo (2) 1 (1952), 343–360

    work page 1952

  4. [4]

    Blumenthal, Theory and applications of distance geometry, Second edition Chelsea Publishing Co., New York 1970 xi+347 pp

    L.M. Blumenthal, Theory and applications of distance geometry, Second edition Chelsea Publishing Co., New York 1970 xi+347 pp

    work page 1970

  5. [5]

    Blumenthal, K

    L.M. Blumenthal, K. Menger, Studies in geometry, W. H. Freeman and Co., San Francisco, Calif. 1970 xiv+512 pp

    work page 1970

  6. [6]

    Cogis, On the Ferrers dimension of a digraph, Discrete Math

    O. Cogis, On the Ferrers dimension of a digraph, Discrete Math. 38 (1982) 47–52

    work page 1982

  7. [7]

    Corominas, Sur les ensembles ordonn´ es projectifs et la propri´ et´ e du points fixe,C.R.Acad.Sc

    E. Corominas, Sur les ensembles ordonn´ es projectifs et la propri´ et´ e du points fixe,C.R.Acad.Sc. Paris, S´ erie A311 (1990), 199-204

    work page 1990

  8. [8]

    Doignon, A

    J.P. Doignon, A. Ducamp, J.C. Falmagne, On realizable biorders and the biorder dimension of a rela- tion, J. Math. Psych. 28(1984) 73–109

    work page 1984

  9. [9]

    Dress, Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups, a note on combinatorial properties of metric spaces, Adv

    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. in Math. 53 (3)(1984), 321-402

    work page 1984

  10. [10]

    Dress, Towards a classification of transitive group actions on finite metric spaces, Adv

    A.W.N. Dress, Towards a classification of transitive group actions on finite metric spaces, Adv. in Math. 74 2 (1989),163-189

    work page 1989

  11. [11]

    Duffus, I

    D. Duffus, I. Rival, A structure theory of ordered sets, J.of Discrete Math. 35 (1981), 53-118

    work page 1981

  12. [12]

    Ehrenfeucht, D

    A. Ehrenfeucht, D. Haussler, G. Rozenberg, On regularity of context-free languages, Theoret. Comput. Sci. 27 (1983), no. 3, 311–332

    work page 1983

  13. [13]

    Fishburn, Interval Orders and Interval Graphs, Wiley, 1985

    P.C. Fishburn, Interval Orders and Interval Graphs, Wiley, 1985

    work page 1985

  14. [14]

    Higman Ordering by divisbility in abstract algebra, Proc

    G. Higman Ordering by divisbility in abstract algebra, Proc. London Math. Soc (3) 2 (1952), 326-336

    work page 1952

  15. [15]

    Hudry, R´ etractions, cor´ etractions et envelope injective d’une alg` ebre de transitions,Discrete Math

    A. Hudry, R´ etractions, cor´ etractions et envelope injective d’une alg` ebre de transitions,Discrete Math. 247 (2002), no. 1-3, 117–134

    work page 2002

  16. [16]

    Hudry, Injective envelope and parallel decomposition of a transition system, Discrete Math

    A. Hudry, Injective envelope and parallel decomposition of a transition system, Discrete Math. 289 (2004), no. 1-3, 45–61

    work page 2004

  17. [17]

    Jawhari, D

    E. Jawhari, D. Misane, M. Pouzet, Retracts graphs and ordered sets from the metric point of view, (I.Rival ed) Contemporary Mathematics, Vol 57,175-226. 1986

    work page 1986

  18. [18]

    Jullien, Sur un th´ eor` eme d’extension dans la th´ eorie des mots,C

    P. Jullien, Sur un th´ eor` eme d’extension dans la th´ eorie des mots,C. R. Acad. Sci. Paris S´ erie A-B 266 (1968) 851–854

    work page 1968

  19. [19]

    Kaarli, S

    K. Kaarli, S. Radeleczki: Representation of integral quantales by tolerances. Algebra Universalis 79 (5) (2018), https://doi.org/10.1007/s00012-018-0484-1

    work page doi:10.1007/s00012-018-0484-1 2018

  20. [20]

    Kabil, M

    M. Kabil, M. Pouzet, Une extension d’un th´ eor` eme de P. Jullien sur les ˆ ages de mots,RAIRO Inform. Th´ eor. Appl. 26 (1992), no. 5, 449–482

    work page 1992

  21. [21]

    Kabil, M

    M. Kabil, M. Pouzet, Ind´ ecomposabilit´ e et irr´ eductibilit´ e dans la vari´ et´ e des r´ etractes absolus des graphes r´ eflexifs,C.R.Acad.Sci. Paris S´ erie A 321 (1995), 499-504

    work page 1995

  22. [22]

    M. Kabil, Une approche m´ etrique de l’ind´ ecomposabilit´ e et de l’irr´ eductibilit´ e dans la vari´ et´ e des r´ etractes absolus des graphes et des syst` emes de transitions , Th` ese de doctorat d’ ´Etat, Universit´ e Hassan II A¨ ın Chock, Casablanca, 19 D´ ecembre 1996

    work page 1996

  23. [23]

    Kabil, M

    M. Kabil, M. Pouzet, Injective envelope of graphs and transition systems, Discrete Math.192 (1998), 145-186

    work page 1998

  24. [24]

    Free monoids and generalized metric spaces

    M. Kabil, M. Pouzet, I.G. Rosenberg, Free monoids and metric spaces, To the memory of Michel Deza, Europ. J. of Combinatorics, Online publication complete: April 2, 2018, https://doi.org/10.1016/j.ejc.2018.02.008. arXiv: 1705.09750v1, 27 May 2017

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1016/j.ejc.2018.02.008 2018

  25. [25]

    Korshunov, The number of monotonic Boolean functions, Problemy Kibern, 38 (1981), 5-108 (Russian), 272, MR 83h : 06012

    A.D. Korshunov, The number of monotonic Boolean functions, Problemy Kibern, 38 (1981), 5-108 (Russian), 272, MR 83h : 06012

    work page 1981

  26. [26]

    Lothaire, Combinatorics on words, Encyclopedia Math

    M. Lothaire, Combinatorics on words, Encyclopedia Math. Appl., 17, Addison-Wesley, 1983

    work page 1983

  27. [27]

    M.Nivat, Personnal communication, 1989

    work page 1989

  28. [28]

    Nowakowski, I

    R. Nowakowski, I. Rival, The smallest graph variety containing all paths, J. of Discrete Math. 43 (1983), 185–198

    work page 1983

  29. [29]

    M. Pouzet, Une approche m´ etrique de la r´ etraction dans les ensembles ordonn´ es 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´ ep. Math. Nouvelle S´ er. B, 85-2, Univ. Claude-Bernard, Lyon, 1985

    work page 1984

  30. [30]

    Pouzet, I.G

    M. Pouzet, I.G. Rosenberg, General metrics and contracting operations, Graphs and combinatorics (Lyon, 1987; Montreal, PQ, 1988). Discrete Math. 130 (1994),103–169

    work page 1987

  31. [31]

    Pouzet, H

    M. Pouzet, H. Si Kaddour, N. Zaguia, Finite dimensional scattered posets, European J. of Combina- torics, 37(2014), 79–99

    work page 2014

  32. [32]

    Riguet, Les relations de Ferrers, C.R.Acad.Sc

    J. Riguet, Les relations de Ferrers, C.R.Acad.Sc. Paris S´ erie A 232 (1951), 1729–1730

    work page 1951

  33. [33]

    Sa¨ ıdane, Graphe et languages: une approche metrique, Th` ese de doctorat, Universit´ e Claude- Bernard, Lyon, Novembre 1991

    F. Sa¨ ıdane, Graphe et languages: une approche metrique, Th` ese de doctorat, Universit´ e Claude- Bernard, Lyon, Novembre 1991. INJECTIVE ENVELOPES AND FERRERS LANGUAGES 23

    work page 1991

  34. [34]

    Sakarovitch, Elements of automata theory, Translated from the 2003 French original by Reuben Thomas

    J. Sakarovitch, Elements of automata theory, Translated from the 2003 French original by Reuben Thomas. Cambridge University Press, Cambridge, 2009

    work page 2003

  35. [35]

    Simon, Piecewise testable events, Automata theory and formal languages (Second GI Conf., Kaiser- slautern, 1975), pp

    I. Simon, Piecewise testable events, Automata theory and formal languages (Second GI Conf., Kaiser- slautern, 1975), pp. 214?222. Lecture Notes in Comput. Sci., Vol. 33, Springer, Berlin, 1975

    work page 1975

  36. [36]

    Stern, Characterizations of some classes of regular events, Theoretical Computer Science 35 (1985) 17–42

    J. Stern, Characterizations of some classes of regular events, Theoretical Computer Science 35 (1985) 17–42

    work page 1985

  37. [37]

    Viennot, Factorisations des mono¨ ıdes,Th` ese de 3`eme cycle, Paris, Janvier 1971

    G. Viennot, Factorisations des mono¨ ıdes,Th` ese de 3`eme cycle, Paris, Janvier 1971

    work page 1971

  38. [38]

    Wiedemann, A computation of the eight Dedekind number, Order 8 (1991), 5–6

    D. Wiedemann, A computation of the eight Dedekind number, Order 8 (1991), 5–6

    work page 1991

  39. [39]

    Wiener, A contribution to the theory of relative position, Proc

    N. Wiener, A contribution to the theory of relative position, Proc. Camb. Philos. Soc. 17 (1914), 441– 449. Laboratoire Math´ematiques et Applications, D´epartement de Math´ematiques, Facult´e des Sci- ences et Techniques, Universit ´e Hassan II -Casablanca, BP 146 Mohammedia, Morocco. E-mail address: kabilfstm@gmail.com Univ. Lyon, Universit´e Claude-Ber...

    work page 1914