Complete representation by partial functions for signatures containing antidomain restriction

We investigate notions of complete representation by partial functions, where the operations in the signature include antidomain restriction and may include composition, intersection, update, preferential union, domain, antidomain, and set difference. When the signature includes both antidomain restriction and intersection, the join-complete and the meet-complete representations coincide. Otherwise, for the signatures we consider, meet-complete is strictly stronger than join-complete. A necessary condition to be meet-completely representable is that the atoms are separating. For the signatures we consider, this condition is sufficient if and only if composition is not in the signature. For each of the signatures we consider, the class of (meet-)completely representable algebras is not axiomatizable by any existential-universal-existential first-order theory. For 14 expressively distinct signatures, we show, by giving an explicit representation, that the (meet-)completely representable algebras form a basic elementary class, axiomatizable by a universal-existential-universal first-order sentence. The signatures we axiomatize are those containing antidomain restriction and any of intersection, update, and preferential union and also those containing antidomain restriction, composition, and intersection and any of update, preferential union, domain, and antidomain.

Authors

Institutions

Publication Details

Journal
International Journal of Algebra and Computation
Published
2024-08-23
DOI
https://doi.org/10.1142/s0218196724500450
Primary Topic
semigroups and automata theory
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Complete representation by partial functions for signatures containing antidomain restriction

Brett McLean
International Journal of Algebra and Computation
semigroups and automata theory
article

Complete representation by partial functions for signatures containing antidomain restriction

Brett McLean
article en

Abstract

We investigate notions of complete representation by partial functions, where the operations in the signature include antidomain restriction and may include composition, intersection, update, preferential union, domain, antidomain, and set difference. When the signature includes both antidomain restriction and intersection, the join-complete and the meet-complete representations coincide. Otherwise, for the signatures we consider, meet-complete is strictly stronger than join-complete. A necessary condition to be meet-completely representable is that the atoms are separating. For the signatures we consider, this condition is sufficient if and only if composition is not in the signature. For each of the signatures we consider, the class of (meet-)completely representable algebras is not axiomatizable by any existential-universal-existential first-order theory. For 14 expressively distinct signatures, we show, by giving an explicit representation, that the (meet-)completely representable algebras form a basic elementary class, axiomatizable by a universal-existential-universal first-order sentence. The signatures we axiomatize are those containing antidomain restriction and any of intersection, update, and preferential union and also those containing antidomain restriction, composition, and intersection and any of update, preferential union, domain, and antidomain.

International Journal of Algebra and ComputationVol. 34(08)
Ghent University (BE)
Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung, Fonds Wetenschappelijk Onderzoek
Reduced inequalities
Openalex Percentile: Top 84%
semigroups and automata theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Complete representation by partial functions for signatures containing antidomain restriction — Brett McLean · International Journal of Algebra and Computation (2024) | TGRS Research Map | TGRS