pith. sign in

arxiv: 2606.19394 · v1 · pith:IPO2YQNQnew · submitted 2026-06-16 · 💻 cs.FL

On Epimorphisms of Hypergraphic Automata and Input Symbol Semigroups

Jasem Hamoud This is my paper

Pith reviewed 2026-06-26 21:40 UTC · model grok-4.3

classification 💻 cs.FL
keywords hypergraphic automataepimorphismsuniversal automatahypergraphsinput symbol semigroupsp*-hypergraphsweak epimorphismsstrong epimorphisms
0
0 comments X

The pith

Epimorphisms of universal hypergraphic automata are characterized by necessary and sufficient conditions on maps between their state and output hypergraphs.

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

The paper seeks a full description of when one universal hypergraphic automaton maps onto another while preserving the structure of inputs, states, and outputs. This description matters because the automata are defined so that their states and outputs form hypergraphs preserved by the transition and output actions, connecting geometric properties of hypergraphs to algebraic properties of input semigroups. The work introduces two notions of epimorphism on hypergraphs, called weak and strong, and proves that these notions coincide exactly when the hypergraphs belong to the subclass of p*-hypergraphs, which includes projective and affine planes. The central result supplies explicit conditions on the three component maps of any candidate epimorphism.

Core claim

The paper introduces weak and strong epimorphisms for hypergraphs and proves that the two notions diverge in general but coincide for every p*-hypergraph. It then states necessary and sufficient conditions for a triple (f, P_s, g) to be an epimorphism of universal hypergraphic automata; these conditions are expressed directly in terms of the action of f on the state hypergraph and of g on the output hypergraph. The same conditions characterize epimorphisms of the associated semigroups of input symbols.

What carries the argument

The triple (f, P_s, g) consisting of a map f on state hypergraphs, a map g on output hypergraphs, and a map P_s on the input-symbol semigroup; the triple is an epimorphism precisely when f and g satisfy the stated compatibility conditions derived from the weak or strong hypergraph epimorphism notions.

If this is right

  • The algebraic structure of the input-symbol semigroup is completely determined once the epimorphisms of the automata are known.
  • When the state and output hypergraphs are projective or affine planes, the weak and strong epimorphism notions become identical, so a single set of conditions suffices.
  • Every epimorphism of universal hypergraphic automata must preserve the universal attracting property through the component maps on the hypergraphs.
  • The characterization extends directly to epimorphisms of the semigroups of input symbols.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The divergence between weak and strong hypergraph epimorphisms outside the p*-class may produce distinct categories of automata whose input semigroups behave differently.
  • The explicit conditions on hypergraph maps could be used to construct new universal hypergraphic automata by transporting known examples along suitable maps.
  • The link between hypergraph geometry and semigroup algebra suggests that combinatorial designs such as planes may yield automata whose input semigroups have previously unrecognized properties.

Load-bearing premise

The state sets and output symbol sets of the automata are hypergraphs that remain invariant under the actions of the transition and output functions.

What would settle it

A pair of universal hypergraphic automata together with a triple of maps that meets every stated condition on the state and output hypergraphs yet fails to be an epimorphism of the automata would falsify the claimed characterization.

Figures

Figures reproduced from arXiv: 2606.19394 by Jasem Hamoud.

Figure 1
Figure 1. Figure 1: Visualisation of Lemma 3.1. We now consider a strengthened version of the result for p-hypergraphs, where every weak epimorphism is automatically a strong epimorphism. Lemma 3.2. Let HY = (Y, LY ) be an effective hypergraph with p-definable edges, let HY1 = (Y1, LY1 ) be a p-hypergraph, and let g : HY → HY1 be a weak epimorphism such that the induced map (f × g) is surjective onto Hom(HX1 , HY1 ) for some … view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of Lemma 3.2: for p-hypergraphs, every weak epi￾morphism is a strong epimorphism. Surjectivity of f × g and the p￾hypergraph axioms imply that every edge of HY1 is the image of an edge of HY . We now state and prove the main theorem for general effective hypergraphs with p￾definable edges. Theorem 3.3. Let HX = (X, LX), HY = (Y, LY ), HX1 = (X1, LX1 ), and HY1 = (Y1, LY1 ) be effective hypergr… view at source ↗
read the original abstract

Hypergraphic automata are automata whose state sets and output symbol sets are hypergraphs invariant under the actions of the transition and output functions. Universally attracting objects in the category of such automata are called universal hypergraphic automata; their semigroups of input symbols are algebras of mappings whose properties are tightly linked to the algebraic structure of the automata themselves. This paper establishes a complete characterisation of epimorphisms of universal hypergraphic automata and of their semigroups of input symbols. A central contribution is the introduction of two distinct notions of epimorphism for hypergraphs including weak, strong and the proof that these notions diverge in general but necessarily coincide for the important subclass of $p^*$-hypergraphs, which includes automata whose state hypergraphs and output hypergraphs are projective or affine planes. The main results give necessary and sufficient conditions for a triple $(f, \mathbb{P}_s, g)$ to be an epimorphism of universal hypergraphic automata, expressed in terms of the component maps on the state and output hypergraphs.

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

0 major / 1 minor

Summary. The paper claims to establish a complete characterisation of epimorphisms of universal hypergraphic automata and of their semigroups of input symbols. It introduces two notions of epimorphism (weak and strong) for hypergraphs, proves that these coincide on the subclass of p*-hypergraphs (including those whose state and output hypergraphs are projective or affine planes), and supplies necessary and sufficient conditions for a triple (f, ℙ_s, g) to be an epimorphism, expressed via the component maps on the state and output hypergraphs.

Significance. If the stated characterisation is correct, the work supplies a concrete link between the categorical structure of hypergraphic automata and the algebraic properties of their input-symbol semigroups. The coincidence result for p*-hypergraphs is a useful technical contribution that applies directly to geometrically defined automata.

minor comments (1)
  1. [Abstract] The abstract asserts a 'complete characterisation' but does not display the explicit conditions; a one-sentence summary of the main criterion would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading and for the accurate summary of our contributions. The positive assessment of significance is appreciated. No specific major comments were raised in the report, despite the 'uncertain' recommendation. We have therefore prepared no point-by-point responses and no revisions. If the uncertainty stems from particular aspects of the characterisation or proofs, we would welcome the opportunity to address them in a revised submission.

Circularity Check

0 steps flagged

No circularity; characterisation is independent

full rationale

The paper defines hypergraphic automata and universal objects, then proves weak/strong epimorphisms coincide on the subclass of p*-hypergraphs and states necessary and sufficient conditions for the triple (f, P_s, g) to be an epimorphism directly in terms of the component maps on state and output hypergraphs. No equations reduce a claimed prediction or result to a fitted parameter or prior self-citation by construction; the conditions are external to the input data and the derivation remains self-contained against the category-theoretic definitions.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract alone supplies insufficient detail to enumerate free parameters, axioms, or invented entities. The work appears to rest on standard definitions from category theory and automata theory.

pith-pipeline@v0.9.1-grok · 5702 in / 1153 out tokens · 32289 ms · 2026-06-26T21:40:26.081427+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

20 extracted references · 12 canonical work pages

  1. [1]

    InProceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

    A. Bretto,Hypergraph Theory: An Introduction, (Springer, Cham, 2013).doi: 10.1007/978-3-319- 00080-0

    work page doi:10.1007/978-3-319- 2013

  2. [2]

    Chiari, D

    M. Chiari, D. Mandrioli, F. Pontiggia, and M. Pradella,Model checking probabilistic operator prece- dence automata, arXiv preprint (2024), arXiv:2404.03515.url: arxiv.org/abs/2404.03515

    arXiv 2024

  3. [3]

    Dennunzio, E

    A. Dennunzio, E. Formenti, D. Grinberg, and L. Margara,From linear to additive cellular automata, in Proc. 47th Int. Colloquium on Automata, Languages, and Programming (ICALP 2020), LIPIcs 168(2020), 125:1–125:13.doi: 10.4230/LIPIcs.ICALP.2020.125

    work page doi:10.4230/lipics.icalp.2020.125 2020

  4. [4]

    Dennunzio, E

    A. Dennunzio, E. Formenti, D. Grinberg, and L. Margara,An efficiently computable characterization of stability and instability for linear cellular automata, J. Comput. Syst. Sci.119(2021), 63–71.doi: 10.1016/j.jcss.2021.03.003

    work page doi:10.1016/j.jcss.2021.03.003 2021

  5. [5]

    Eilenberg,Automata, Languages, and Machines, Vol

    S. Eilenberg,Automata, Languages, and Machines, Vol. A, (Academic Press, New York, 1974)

    1974

  6. [6]

    Fijalkow, C

    N. Fijalkow, C. Riveros, and J. Worrell,Probabilistic automata of bounded ambiguity, Information and Computation282(2022), 104648.doi: 10.1016/j.ic.2020.104648

    work page doi:10.1016/j.ic.2020.104648 2022

  7. [7]

    Geißler and T

    D. Geißler and T. Winkler,Weighted automata for exact inference in discrete probabilistic programs, in Theoretical Aspects of Computing – ICTAC 2025, Lecture Notes in Computer Science16237 (2025).doi: 10.1007/978-3-032-11176-016

    work page doi:10.1007/978-3-032-11176-016 2025

  8. [8]

    Hartshorne,Foundations of Projective Geometry, (Ishi Press, New York, 2009)

    R. Hartshorne,Foundations of Projective Geometry, (Ishi Press, New York, 2009)

    2009

  9. [9]

    Hensel, S

    C. Hensel, S. Junges, J.-P. Katoen, T. Quatmann, and M. Volk,The probabilistic model checker Storm, Int. J. Softw. Tools Technol. Transfer24(2022), no. 4, 589–610.doi: 10.1007/S10009-021- 00633-Z

    work page doi:10.1007/s10009-021- 2022

  10. [10]

    T. A. Henzinger, A. Prakash, and K. S. Thejaswini,Resolving nondeterminism with randomness, in Proc. 50th Int. Symp. Mathematical Foundations of Computer Science (MFCS 2025), LIPIcs (2025). doi: 10.4230/LIPIcs.MFCS.2025.57

    work page doi:10.4230/lipics.mfcs.2025.57 2025

  11. [11]

    Karteszi,Introduction to Finite Geometries, (North Holland, 2014)

    F. Karteszi,Introduction to Finite Geometries, (North Holland, 2014)

    2014

  12. [12]

    E. V. Khvorostukhina and V. A. Molchanov,On problem of concrete characterization of universal automata, Lobachevskii J. Math.38(2017), 664–669.doi: 10.1134/S1995080217040114

    work page doi:10.1134/s1995080217040114 2017

  13. [13]

    E. V. Khvorostukhina,On monomorphisms of universal hypergraphic automata, Lobachevskii J. Math. (2025).doi: 10.1134/S1995080225614109

    work page doi:10.1134/s1995080225614109 2025

  14. [14]

    Lallement,Semigroups and Combinatorial Applications, (Wiley, New York, 1979)

    G. Lallement,Semigroups and Combinatorial Applications, (Wiley, New York, 1979)

    1979

  15. [15]

    A. I. Malcev,Algebraic Systems, (Springer, Berlin, 1973).doi: 10.1007/978-3-642-65374-2

    work page doi:10.1007/978-3-642-65374-2 1973

  16. [16]

    V. A. Molchanov and E. V. Khvorostukhina,On problem of abstract definability of universal hy- pergraphic automata by input symbol semigroup, Chebyshev. Sb.20(2019), no. 2, 251–264.doi: 10.22405/2226-8383-2019-20-2-251-264

    work page doi:10.22405/2226-8383-2019-20-2-251-264 2019

  17. [17]

    B.I.Plotkin, L.Ja.Geenglaz, andA.A.Gvaramija,Algebraic Structures in Automata and Databases Theory, (World Scientific, Singapore, 1992)

    1992

  18. [18]

    Béaur, J

    P. Béaur, J. KariDecidability in group shifts and group cellular automata, in Proc. 45th Int. Symp. Mathematical Foundations of Computer Science (MFCS 2020), LIPIcs170(2020), 72:1–72:13

    2020

  19. [19]

    V. V. Vagner,The theory of relations and the algebra of partial mappings, in The Theory of Semi- groups and Their Applications, Vol. 1, 3–178 (Saratov University, Saratov, 1965)

    1965

  20. [20]

    Zykov,Hypergraphs, Uspekhi Mat

    A. Zykov,Hypergraphs, Uspekhi Mat. Nauk29(1974), no. 6, 89–156.doi: 10.1070/RM1974v029n06ABEH001303. Jasem Hamoud:Department of Discrete Mathematics, Moscow Institute of Physics and Technology Email address:hamoud.math@gmail.com

    work page doi:10.1070/rm1974v029n06abeh001303 1974