PaperlayerView exact revision on arXiv

Source-linked AI summary

Languages and Recognition in a Category with Factorisation

Harsh Beohar, Mike Cruchten, Georg Struth

arXiv:2609.04346v1cs.FLcs.LO

TL;DR

Language recognition is central to algebraic language theory, and the paper motivates a categorical account by the reindexing of languages and recognising maps across alphabets. It builds that account with fibrations over T-algebras and provides conditions for syntactic quotients and regular-language closure under certain limits and colimits.

  • Problem

    The paper asks how language recognition can be described categorically across alphabets, where both languages and their recognising maps reindex along homomorphisms.

    Source: §1 · p. 1

  • Method

    The framework replaces monoids with T-algebras, treats left morphisms that are T-morphisms as quotients, and organises languages and their recognition in fibrations.

    Source: §1 · p. 2

  • Results

    The paper establishes sufficient conditions for syntactic quotients and for regular languages to form a fibration and be closed under certain limits and colimits.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Recognition is stable under reindexing in this fibrational framework.

    Source: §7 · p. 21

    The paper treats Słomiński’s construction only for varieties, leaves algebraic closure properties for future work, and notes that its language definition depends on the choice of Ω.

    Source: §7 · p. 21

Abstract

from arXiv · show

Language recognition by homomorphisms is a central construction of algebraic language theory. Initially studied for monoids and semigroups, it has subsequently been expanded to other algebraic structures. Our new categorical account is based on fibrations, which have already seen other applications in automata theory. Languages and surjective homomorphisms give indeed rise to two fibrations, and the notion of language recognition is stable under reindexing. We develop this framework in a category with a factorisation system and address two main technical questions in the fibrational setting. First, we provide sufficient conditions under which languages have syntactic quotients (which is a generalisation of syntactic congruences) and we show how such quotients can be described in some concrete cases using a result by Slomi\'nski. Second, we introduce sufficient conditions under which (regular) languages are closed under certain J-limits and J-colimits.

1 Introduction

The paper gives a fibrational account of language recognition, motivated by the reindexing of languages and their recognising maps across alphabets. It develops that account using T-algebras and a factorisation structure, and establishes conditions for syntactic quotients and closure properties of regular languages.

1 Introduction

  • The central contribution is a fibrational account of language recognition that models how languages and their recognising maps reindex across alphabets.The motivation is that inverse images preserve regular languages, while recognising maps can also be reindexed along the corresponding homomorphism.Source: §1 · p. 1
  • The framework replaces monoids with T-algebras and uses left morphisms that are T-morphisms as quotients and recognisers.The quotient category forms a fibration when T preserves left morphisms; languages are characteristic functions into a fixed object, and language and recognition fibrations encode recognition by quotients.Source: §1 · p. 2
  • The paper gives sufficient conditions for syntactic quotients in a category with a factorisation system, generalising syntactic congruences.For a proper factorisation system, these conditions follow from earlier results by Adámek.Source: §1 · p. 2
  • Słomiński’s interior operator explicitly describes syntactic quotients in the concrete cases considered, including algebras and ordered algebras over a finitary signature.The operator is defined using the internal language of fibrations and Słomiński’s elementary translations.Source: §1 · p. 2
  • The paper identifies conditions for regular languages to form a fibration and to be closed under certain limits and colimits.The closure result is stated for a distinguished class of finite objects.Source: §1 · p. 2
  • Unlike the framework in, this approach allows weaker assumptions, including non-commutative monads, and its specific use of fibrations for algebraic language recognition is claimed as novel.The paper also distinguishes its syntactic-quotient result from by obtaining a right adjoint to the forgetful functor; earlier fibrational work in automata theory is acknowledged.Source: §1 · pp. 1–3

2 Preliminaries

The preliminaries fix notation and recall factorisation systems and fibred categories, assuming familiarity with basic category theory. They define the reindexing structure used later and illustrate it with the domain fibration.

2 Preliminaries

  • A factorisation system specifies left and right morphisms, factors every morphism as a left morphism followed by a right morphism, and has a unique filler property; it is proper when the classes lie within epis and monos.The classes contain isomorphisms and are closed under composition.Source: §2 · p. 3
  • A fibration provides Cartesian lifts for base morphisms; its fibre over an object consists of objects and morphisms mapping to that object and its identity.For a cloven fibration, a base morphism induces a reindexing functor between fibres.Source: §2 · p. 4
  • A cleavage chooses Cartesian lifts, making a fibration cloven.The chosen lift over u is written u*(Y) → Y.Source: §2 · p. 4
  • A cloven fibration yields an indexed category, and conversely an indexed category induces a fibration through the Grothendieck construction.The construction uses pairs of base objects and fibre objects, with morphisms defined using reindexing.Source: §2 · p. 4
  • Fibred J-limits and J-colimits require such limits and colimits in each fibre and their preservation under reindexing.Source: §2 · p. 4
  • The domain functor from the arrow category is a cloven fibration whose fibre over J is isomorphic to the coslice category J/C.Its Cartesian lift reindexes an arrow f by composition with the base morphism.Source: §2 · pp. 4–5

3 Quotients

The section builds a fibration of algebra quotients under a preservation condition, then identifies quotient fibres with familiar congruence structures in concrete settings. These examples also show limits can be preserved while arbitrary colimits need not be.

3.1 The Quotient Fibration

  • When T preserves left morphisms, the domain functor from the category of quotients is a fibration.Reindexing is obtained by factoring the composite of a quotient with an algebra morphism.Source: §3.1 · p. 5

3.2 Examples

  • The quotient construction applies to monads on Set and Pos and to the endofunctor whose algebras are deterministic semiautomata.The framework also covers strongly finitary monads on Pos, corresponding to varieties of ordered algebras.Source: §3.2 · pp. 8–9
  • For finitary monads on Set, quotient fibres correspond to congruences and are bicomplete; ordered-algebra fibres correspond to precongruences and are also bicomplete.In the ordered case, the quotient fibre is equivalent to the complete lattice of precongruences.Source: §3.2 · pp. 8–9
  • In the Set examples, the quotient fibration has fibred limits, but reindexing need not preserve arbitrary colimits.For the identity monad and h: 2 →1, the inverse image of the initial equivalence relation on 1 is not the initial equivalence relation on 2.Source: §3.2 · p. 8
  • For the initial semiautomaton, the quotient fibre is the category of reachable semiautomata and is equivalent to the lattice of right congruences on A∗.The fibre is also bicomplete.Source: §3.2 · p. 10

4 The Language and Recognition Fibrations

The section combines languages and quotients in a categorical framework for recognition. It defines language and recognition fibrations, establishes a condition for recognition to be stable under reindexing, and instantiates the framework in Set, Pos, and semiautomata.

4 The Language and Recognition Fibrations

  • A language over a T-algebra is a morphism into a fixed object Ω, and a quotient recognises it when the language factors through that quotient.The language fibration is formed from the category of languages over T-algebras.Source: §4 · pp. 10–11
  • The recognition fibration has fibres consisting of quotient-language pairs in which the quotient recognises the language.Related fibrations fix either a quotient and collect its recognised languages, or fix a language and collect its recognising quotients.Source: §4 · pp. 11–12
  • When language reindexing is composition, reindexing a quotient that recognises a language yields a quotient recognising the reindexed language.This condition makes recognition stable under reindexing and supports the recognition fibration.Source: §4 · p. 11
  • In Set, languages are subsets and reindex by inverse image; in Pos, they are up-closed subsets and also reindex by inverse image.The Set language fibration has fibred limits and colimits; the Pos language fibration does as well.Source: §4 · p. 12
  • For semiautomata, recognition by a quotient specializes to standard acceptance by an automaton, and the framework uniformly instantiates classical automata and algebraic language concepts.The account also includes ordered automata, Wilke algebras, and lasso automata.Source: §4 · p. 13

5 Syntactic Quotients

Syntactic quotients capture the smallest recognizing quotient of a language. The section gives conditions for their existence and develops a translation-based construction that recovers familiar congruences in concrete settings.

5 Syntactic Quotients

  • A syntactic quotient is the terminal recognizer of a language, through which every other recognizing quotient factors uniquely.A weakly syntactic quotient requires such a factorization without uniqueness.Source: §5 · p. 13

5.1 Existence of Syntactic Quotients

  • If the underlying object U A has a right adjoint, every language has a weakly syntactic quotient, and it has a syntactic quotient when L ⊆ E.Source: §5.1 · p. 14
  • If C is co-well-powered, CoSubA has arbitrary joins, and T preserves them, U A has a right adjoint; the cited examples therefore admit syntactic quotients for every language.Source: §5.1 · pp. 15–16

5.2 Słomiński’s Construction

  • For finitary monads on Set, Słomiński’s translation-based construction gives a right adjoint that returns the greatest congruence contained in an equivalence relation.The construction describes the right adjoint using translations as an interior operator.Source: §5.2 · pp. 16–17
  • On A*, translations test all two-sided contexts, recovering the classical syntactic congruence; suffix translations yield the Myhill–Nerode congruence for semiautomata.Source: §5.2 · p. 17
  • The construction extends to strongly finitary monads on Pos and finitary monads on Set^k, deriving ordered Myhill–Nerode and Wilke congruences; the Wilke setting assumes infinite-word membership is determined by ultimately periodic words.Source: §5.2 · pp. 17–18

6 Properties of Recognition and (Regular) Languages

The section defines regular languages through finite-codomain quotients and gives conditions for closure under limits and colimits. It derives specific closure results in Set and Pos, including a boundary on complementation.

6 Properties of Recognition and (Regular) Languages

  • Regular languages are those recognized by finite-codomain quotients; if right morphisms reflect finiteness, these quotients form a subfibration and recognizers are down-closed.The subfibration condition supports the section’s uniform treatment of closure properties.Source: §6 · pp. 18–19
  • The forgetful functor creates all non-empty limits in the recognition fibre and, if that fibre has a weakly terminal object, all non-empty colimits.The result concerns the category of recognizers for a fixed language.Source: §6 · p. 19
  • A language is regular exactly when the right adjoint applied to the terminal recognizer yields a finite quotient, under the stated adjunction, terminal-object, and upward-closure assumptions.This connects regularity to finiteness of the language’s syntactic quotient.Source: §6 · p. 19
  • If each finite-quotient fibre has cones for diagrams of size |J| and the language fibration has fibred J-limits or J-colimits, regular languages have the corresponding limits or colimits; the result also lifts to the regular-language fibration.The global result assumes the finite-quotient fibration has the required cones in each fibre.Source: §6 · p. 20
  • In Set, regular languages are closed under finite intersections and unions, and under complementation because language fibres are complemented and reindexing preserves complementation.The finite-index congruences saturating a language have finite meets and arbitrary non-empty joins; regularity is equivalent to its syntactic congruence having finite index.Source: §6 · pp. 19–20
  • In Pos, regular languages are not necessarily closed under complementation because each language fibre is a lattice but not a Boolean algebra.The other results of the Set example apply in this setting.Source: §6 · p. 20

7 Conclusion

The conclusion presents a fibrational account of language recognition by quotients, with recognition stable under reindexing, and reports results on syntactic quotients and regular-language closure. It also identifies further work on extending the fibrational treatment and exploring algebraic and quantitative language notions.

7 Conclusion

  • Recognition by quotients is treated fibrationally, with sufficient conditions for quotient and language fibrations and a combined recognition fibration that supports stability under reindexing.The account is developed for a monad on a category equipped with a factorisation system.Source: §7 · p. 21
  • The paper proves an existence theorem for syntactic quotients and relates the fibrational account of Słomiński’s construction to syntactic congruences in ordered monoids and Wilke algebras.The construction is analysed for paradigmatic instances.Source: §7 · p. 21
  • Further work includes a fully fibrational treatment of Słomiński’s construction beyond varieties, algebraic closure properties, and quantitative language notions such as formal power series.The paper currently discusses the construction only for varieties, including ordered and multisorted varieties.Source: §7 · p. 21
Loading 2609.04346v1…