On the structure and theory of McCarthy algebras

Sintesi Tecnica: Sulla Struttura e la Teoria delle Algebre di McCarthy

Problema
Le algebre di McCarthy costituiscono il corrispettivo algebrico della logica di McCarthy, una logica a tre valori basata sulla congiunzione non commutativa utilizzata per modellare la valutazione pigra (lazy evaluation) di predicati parziali nell'informatica (ad es. in Haskell, OCaml, Java e Python). Sebbene l'utilità della logica di McCarthy nelle algebre di processi per modellare la gestione degli errori e le guardie condizionali sia consolidata, la sua struttura algebrica è rimasta poco esplorata. Nello specifico, mentre Guzmán e Squier [13] hanno fornito una base finita per il ridotto privo di costanti (algebre condizionali o C-algebre), e Konikowska [18] ha proposto un elenco di identità per l'algebra a tre elementi $M_3$, mancava un'analisi strutturale completa e una base equazionale ridotta per la varietà completa delle algebre di McCarthy (incluse le costanti). Inoltre, era necessaria una chiarificazione della relazione tra le algebre di McCarthy e altre logiche non classiche (come le logiche di Kleene e le algebre di Boole) all'interno di un quadro algebrico unificato.

Metodologia
Gli autori introducono un quadro algebrico generale chiamato i-ubands (bande unitali con involuzione). Un i-uband è definito come un monoide idempotente $\langle M, \cdot, e \rangle$ dotato di un'operazione unaria involutiva $'$ che soddisfa $x'' \approx x$. Questa struttura funge da terreno comune per varie logiche non classiche, incluse le algebre di Boole, le ortolattici, le algebre di De Morgan e le algebre di Kleene.

La metodologia procede come segue:

1. Definizione e Classificazione: Gli autori analizzano la varietà degli i-ubands, concentrandosi specificamente sugli i-ubands subclassici (quelli che contengono l'algebra di Boole a due elementi come sottualgebra). Classificano tutti gli i-ubands non isomorfi a tre elementi, identificando quattro modelli subclassici: l'algebra debole di Kleene ($WK$), l'algebra forte di Kleene ($SK$), l'algebra di McCarthy ($M_3$) e la sua speculare $M_3^{op}$.
2. Analisi delle Identità: Il saggio investiga le identità soddisfatte da $M_3$ nel contesto degli i-ubands. Ciò comporta la derivazione di leggi di distribuzione debole (distributività a sinistra, ortodistributività), leggi di assorbimento debole e leggi commutative deboli (commutatività dell'unità locale).
3. Assiomatizzazione: Analizzando l'interazione di queste identità, gli autori derivano basi equazionali ridotte ed equivalenti per la varietà delle albre di McCarthy.
4. Decomposizione Strutturale: Gli autori utilizzano l'ordine parziale indotto dall'operazione di addizione ($+$) per decomporre le algebre di McCarthy. Definiscono uno "scheletro semilattice" e delle "fibre" per stabilire un teorema di decomposizione semilattice.
5. Rappresentazione: La struttura algebrica è caratterizzata tramite poseti decorati con sℓ (insiemi parzialmente ordinati decorati con uno scheletro semilattice), dimostrando che le operazioni sono unicamente determinate dall'ordine e dall'appartenenza allo scheletro.

Contributi Chiave e Risultati

• Quadro Unificato (i-ubands): Il saggio stabilisce gli i-ubands come un contesto generale per lo studio di versioni non commutative di logiche classiche e non classiche. Chiarisce la distinzione tra i-ubands e i semigruppi a involuzione con banda, notando che gli i-ubands richiedono solo $x'' \approx x$ anziché la più forte condizione $(xy)' \approx y'x'$.
• Assiomatizzazione Ridotta: Gli autori forniscono una base equazionale finita per la varietà $\mathcal{M}$ delle algebre di McCarthy. Dimostrano che $\mathcal{M}$ coincide con la varietà delle algebre MK (algebre di McCarthy-Konikowska). La base è presentata in termini di tre componenti:
  1. Distributività Debole: Almeno una tra la distributività a sinistra con decomposizione a sinistra, la divisibilità a sinistra con ortodistributività a destra, o la paradistributività a destra.
  2. Assorbimento Debole: Almeno una tra la limitatezza a sinistra o l'assorbimento a sinistra.
  3. Commutatività Debole: Almeno una tra la commutatività dell'unità locale, la commutatività locale o la commutatività wk.
     Questo risultato conferma che i postulati di Konikowska formano una base equazionale e fornisce formulazioni alternative e ridotte.
• Membri Subdirettamente Irriducibili: Il saggio dimostra che le uniche algebre di McCarthy subdirettamente irriducibili sono l'algebra di Boole a due elementi ($2$) e l'algebra di McCarthy a tre elementi ($M_3$). Di conseguenza, la varietà $\mathcal{M}$ è generata da $M_3$.
• Decomposizione Semilattice: Un risultato centrale è il Teorema di Decomposizione Semilattice (Teorema 6.1). Ogni algebra di McCarthy $A$ si decompone in un sistema diretto semilattice di algebre di Boole $\langle I_A, \mathcal{B}_A, \mathcal{P}_A \rangle$, dove:
  • $I_A$ è lo scheletro semilattice di $A$ (isomorfo all'insieme delle unità locali $\{x \cdot 0 \mid x \in A\}$).
  • $\mathcal{B}_A$ è l'insieme delle fibre (intervalli $[0_i, 1_i]$), ciascuna delle quali è un'algebra di Boole.
  • $\mathcal{P}_A$ consiste in omomorfismi tra le fibre indotti dall'ordine.
    A differenza delle normali somme semilattice (ad es. i semigruppi di Clifford), questa decomposizione non è generalmente un quoziente dell'algebra, distinguendosi dai classici teoremi di decomposizione semilattice.
• Rappresentazione come Poseti Decorati: Gli autori mostrano che le algebre di McCarthy sono interamente determinate dai loro poseti decorati con sℓ. Le operazioni (moltiplicazione, involuzione) possono essere espresse utilizzando l'ordine, i supremi/infimi esistenti e un predicato unario che identifica lo scheletro semilattice. Ciò conduce a una caratterizzazione dell'isomorfismo: due algebre di McCarthy sono isomorfe se e solo se i loro poseti decorati con sℓ sono isomorfi.
• Reticolo delle Sottovarietà: Il saggio delinea i livelli inferiori del reticolo delle sottovarietà degli i-ubands. Identifica che le algebre di McCarthy formano una varietà subclassica (dove l'unità non è un punto fisso dell'involuzione) e che $\mathcal{M}$ copre la varietà delle algebre di Boole ($BA$) in questo reticolo. Identifica inoltre problemi aperti riguardanti l'assiomatizzazione finita delle varietà generate dal ridotto del monoide di Sugihara ($C_3^s$) e dalle sue varianti sinistra/destra ($L_3^s, R_3^s$).

Significatività
Il saggio fornisce la prima analisi strutturale completa delle algebre di McCarthy, andando oltre l'identificazione della loro base equazionale per arrivare a una comprensione profonda della loro architettura interna. Introducendo gli i-ubands, gli autori unificano lo studio della logica di McCarthy con altre logiche non classiche, rivelando la logica di McCarthy come la compagna non commutativa delle logiche di Kleene e di Boole. Il teorema di decomposizione e la rappresentazione tramite poseti decorati offrono nuovi strumenti per analizzare queste algebre, facilitando potenzialmente ulteriori ricerche nella loro teoria dei modelli e nelle loro applicazioni nell'informatica, in particolare nella verifica formale di processi che coinvolgono la gestione degli errori e la valutazione pigra. Il lavoro chiarisce inoltre la posizione precisa delle algebre di McCarthy nel panorama più ampio delle algebre di Boole e nel reticolo delle sottovarietà degli i-ubands.