Stability of Boolean function classes with respect to clones of linear functions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917707697356800 |
|---|---|
| author | Couceiro, Miguel Lehtonen, Erkko |
| author_facet | Couceiro, Miguel Lehtonen, Erkko |
| contents | We consider classes of Boolean functions stable under compositions both from the right and from the left with clones. Motivated by the question how many properties of Boolean functions can be defined by means of linear equations, we focus on stability under compositions with the clone of linear idempotent functions. It follows from a result by Sparks that there are countably many such linearly definable classes of Boolean functions. In this paper, we refine this result by completely describing these classes. This work is tightly related with the theory of function minors, stable classes, clonoids, and hereditary classes, topics that have been widely investigated in recent years by several authors including Maurice Pouzet and his coauthors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2101_06691 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Stability of Boolean function classes with respect to clones of linear functions Couceiro, Miguel Lehtonen, Erkko Rings and Algebras We consider classes of Boolean functions stable under compositions both from the right and from the left with clones. Motivated by the question how many properties of Boolean functions can be defined by means of linear equations, we focus on stability under compositions with the clone of linear idempotent functions. It follows from a result by Sparks that there are countably many such linearly definable classes of Boolean functions. In this paper, we refine this result by completely describing these classes. This work is tightly related with the theory of function minors, stable classes, clonoids, and hereditary classes, topics that have been widely investigated in recent years by several authors including Maurice Pouzet and his coauthors. |
| title | Stability of Boolean function classes with respect to clones of linear functions |
| topic | Rings and Algebras |
| url | https://arxiv.org/abs/2101.06691 |