On the structure and theory of McCarthy algebras

Technische Samenvatting: Over de Structuur en Theorie van McCarthy-algebra's

Probleemstelling
McCarthy-algebra's vormen het algebraïsche tegenovergestelde van McCarthy-logica, een driedalige logica gebaseerd op niet-commutatieve conjunctie die wordt gebruikt om de luie evaluatie (lazy evaluation) van partiële predicaten in de informatica (bijv. in Haskell, OCaml, Java en Python) te modelleren. Hoewel het nut van McCarthy-logica in procesalgebra's voor het modelleren van foutafhandeling en conditionele guards gevestigd is, is de algebraïsche structuur ervan onderbelicht gebleven. Specifiek ontbrak, hoewel Guzmán en Squier [13] een eindige basis leverden voor de constante-vrije reduct (Conditionele algebra's of C-algebra's), en Konikowska [18] een lijst met identiteiten voor de driedalige algebra $M_3$ voorstelde, een uitgebreide structurele analyse en een gereduceerde equationele basis voor de volledige variëteit van McCarthy-algebra's (inclusclusief constanten). Bovendien vereiste de relatie tussen McCarthy-algebra's en andere niet-klassieke logica's (zoals Kleene-logica's en Booleaanse algebra's) binnen een verenigd algebraïsch kader verduidelijking.

Methodologie
De auteurs introduceren een algemeen algebraïsch kader genaamd i-ubands (unital bands met involutie). Een i-uband wordt gedefinieerd als een idempotente monoïde $\langle M, \cdot, e \rangle$ uitgerust met een unaire involutieve operatie $'$ waarvoor $x'' \approx x$ geldt. Deze structuur dient als een gemeenschappelijke grond voor diverse niet-klassieke logica's, waaronder Booleaanse algebra's, ortholattices, De Morgan-algebra's en Kleene-algebra's.

De methodologie verloopt als volgt:

1. Definitie en Classificatie: De auteurs analyseren de variëteit van i-ubands, waarbij ze zich specifiek richten op subklassieke i-ubands (die de tweedalige Booleaanse algebra als subalgebra bevatten). Ze classificeren alle niet-isomorfe driedalige i-ubands en identificeren vier subklassieke modellen: de zwakke Kleene-algebra ($WK$), de sterke Kleene-algebra ($SK$), de McCarthy-algebra ($M_3$) en haar spiegelbeeld $M_3^{op}$.
2. Identiteitsanalyse: Het artikel onderzoekt de identiteiten die door $M_3$ worden vervuld binnen de context van i-ubands. Dit omvat het afleiden van zwakke distributieve wetten (links-distributiviteit, ortho-distributiviteit), zwakke absorptiewetten en zwakke commutatieve wetten (lokale-eenheid commutativiteit).
3. Axiomatisering: Door de interactie van deze identiteiten te analyseren, leiden de auteurs gereduceerde en equivalente equationele bases af voor de variëteit van McCarthy-algebra's.
4. Structurele Decompositie: De auteurs maken gebruik van de partiële ordening geïnduceerd door de opteloperatie ($+$) om McCarthy-algebra's te decomponeren. Ze definiëren een "semilattice skeleton" (halftelverband-skelet) en "fibers" (vezels) om een semilattice-decompositietheorema vast te stellen.
5. Representatie: De algebraïsche structuur wordt gekarakteriseerd via sℓ-gedecoreerde posets (gedeeltelijk geordende verzamelingen gedecoreerd met een semilattice-skelet), waarbij wordt aangetoond dat de operaties uniek worden bepaald door de ordening en de lidmaatschap van het skelet.

Kernbijdragen en Resultaten

• Verenigd Kader (i-ubands): Het artikel vestigt i-ubands als een algemene setting voor het bestuderen van niet-commutatieve versies van klassieke en niet-klassieke logica's. Het verheldert het onderscheid tussen i-ubands en involutie band semigroepen, waarbij wordt opgemerkt dat i-ubands alleen $x'' \approx x$ vereisen in plaats van de sterkere $(xy)' \approx y'x'$.
• Gereduceerde Axiomatisering: De auteurs bieden een eindige equationele basis voor de variëteit $\mathcal{M}$ van McCarthy-algebra's. Ze bewijzen dat $\mathcal{M}$ samenvalt met de variëteit van MK-algebra's (McCarthy-Konikowska algebra's). De basis wordt gepresenteerd in termen van drie componenten:
  1. Zwakke Distributiviteit: Ten minste één van links-distributiviteit met links-decompositie, links-deelbaarheid met rechts-orthodistributiviteit, of rechts-paradistributiviteit.
  2. Zwakke Absorptie: Ten minste één van links-begrensdheid of links-absorptie.
  3. Zwakke Commutativiteit: Ten minste één van lokale-eenheid commutativiteit, lokale commutativiteit, of wk-commutativiteit.
     Dit resultaat bevestigt dat de postulaten van Konikowska een equationele basis vormen en biedt alternatieve, gereduceerde formuleringen.
• Subdirect Irreduceerbare Leden: Het artikel bewijst dat de enige subdirect irreducibele McCarthy-algebra's de tweedalige Booleaanse algebra ($2$) en de driedalige McCarthy-algebra ($M_3$) zijn. Bijgevolg wordt de variëteit $\mathcal{M}$ gegenereerd door $M_3$.
• Semilattice Decompositie: Een centraal resultaat is de Semilattice Decompositietheorema (Theorem 6.1). Elke McCarthy-algebra $A$ decomponeert in een semilattice direct systeem van Booleaanse algebra's $\langle I_A, \mathcal{B}_A, \mathcal{P}_A \rangle$, waarbij:
  • $I_A$ het semilattice-skelet van $A$ is (isomorf met de verzameling lokale eenheden $\{x \cdot 0 \mid x \in A\}$).
  • $\mathcal{B}_A$ de verzameling vezels (intervallen $[0_i, 1_i]$) is, die elk een Booleaanse algebra vormen.
  • $\mathcal{P}_A$ bestaat uit homomorfismen tussen vezels geïnduceerd door de ordening.
    In tegenstelling tot standaard semilattice sommen (bijv. Clifford-semigroepen), is deze decompositie over het algemeen geen quotient van de algebra, wat het onderscheidt van klassieke semilattice decompositietheorema's.
• Representatie als Gedecoreerde Posets: De auteurs tonen aan dat McCarthy-algebra's volledig worden bepaald door hun sℓ-gedecoreerde posets. De operaties (vermenigvuldiging, involutie) kunnen worden uitgedrukt met behulp van de partiële ordening, bestaande suprema/infima, en een unaire predicaat dat het semilattice-skelet identificeert. Dit leidt tot een karakterisering van isomorfisme: twee McCarthy-algebra's zijn isomorf als en slechts als hun sℓ-gedecoreerde posets isomorf zijn.
• Lattice van Subvariëteiten: Het artikel schetst de lagere niveaus van de lattice van subvariëteiten van i-ubands. Het identificeert dat McCarthy-algebra's een subklassieke variëteit vormen (waarbij de eenheid geen involutie-vastpunt is) en dat $\mathcal{M}$ de variëteit van Booleaanse algebra's ($BA$) in deze lattice bedekt. Het identificeert ook open problemen met betrekking tot de eindige axiomatisering van de variëteiten gegenereerd door de Sugihara-monoïde reduct ($C_3^s$) en zijn links/rechts varianten ($L_3^s, R_3^s$).

Significantie
Het artikel biedt de eerste uitgebreide structurele analyse van McCarthy-algebra's, waarbij verder wordt gegaan dan de identificatie van hun equationele basis naar een diep begrip van hun interne architectuur. Door de introductie van i-ubands verenigen de auteurs de studie van McCarthy-logica met andere niet-klassieke logica's, waarbij zij McCarthy-logica presenteren als de niet-commutatieve metgezel van Kleene- en Booleaanse logica's. De decompositietheorema en de representatie via gedecoreerde posets bieden nieuwe instrumenten voor het analyseren van deze algebra's, wat potentieel verdere research naar hun modeltheorie en toepassingen in de informatica kan faciliteren, met name in de formele verificatie van processen die betrokken zijn bij foutafhandeling en luie evaluatie. Het werk verheldert ook de exacte positie van McCarthy-algebra's binnen het bredere landschap van de algebraïsche logica, specifiek hun relatie tot Booleaanse algebra's en de lattice van subvariëteiten van i-ubands.