Lune

LICS2021Top-tier venue

An Algebraic Characterisation of First-Order Logic with Neighbour

Amaldev Manuel, Dhruv Nevatia

Abstract

We give an algebraic characterisation of first-order logic with the neighbour relation, on finite words. For this, we consider languages of finite words over alphabets with an involution on them. The natural algebras for such languages are involution semigroups. To characterise the logic, we define a special kind of semidirect product of involution semigroups, called the locally hermitian product. The characterisation theorem for FO with neighbour states that a language is definable in the logic if and only if it is recognised by a locally hermitian product of an aperiodic commutative involution semigroup, and a locally trivial involution semigroup. We then define the notion of involution varieties of languages, namely classes of languages closed under Boolean operations, quotients, involution, and inverse images of involutory morphisms. An Eilenberg-type correspondence is established between involution varieties of languages and pseudovarieties of involution semigroups.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Characterization and Decidability of FC-Definable Regular LanguagesSam M. Thompson, Nicole Schweikardt, Dominik D. FreydenbergerLICS 2025
  2. Extensions of ω-Regular LanguagesMikolaj Bojanczyk, Edon Kelmendi, Rafal Stefanski, Georg ZetzscheLICS 2020
  3. The Regular Languages of First-Order Logic with One AlternationCorentin Barloy, Michaël Cadilhac, Charles Paperman, Thomas ZeumeLICS 2022 · 1 citation
  4. On Logics and Homomorphism ClosureManuel Bodirsky, Thomas Feller, Simon Knäuer, Sebastian RudolphLICS 2021 · 2 citations
  5. Linear-Algebraic Models of Linear Logic as Categories of Modules over Σ-Semirings✱Takeshi Tsukada, Kazuyuki AsadaLICS 2022 · 4 citations
Dusk over the sea between two cliffs drawn in fine vertical lines