Linearly definable classes of boolean functions

Miguel Couceiro; Erkko Lehtonen

Linearly definable classes of boolean functions

Miguel Couceiro, Erkko Lehtonen

Mathematics

Université de Lorraine

Research output: Contribution to journal › Conference article › peer-review

1 Scopus citations

Abstract

In this paper we address the question “How many properties of Boolean functions can be defined by means of linear equations?” 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 and stable classes, a topic that has been widely investigated in recent years by several authors including Maurice Pouzet.

Original language	British English
Pages (from-to)	21-28
Number of pages	8
Journal	CEUR Workshop Proceedings
Volume	2925
State	Published - 2020
Event	1st International Conference "Algebras, Graphs and Ordered Sets", ALGOS 2020 - Virtual, Online Duration: 26 Aug 2020 → 28 Aug 2020

Keywords

Boolean function
Clone
Clonoid
Functional equation
Linear definability

Cite this

@article{1dab601f01544470a5bd6ca655ad32e2,

title = "Linearly definable classes of boolean functions",

abstract = "In this paper we address the question “How many properties of Boolean functions can be defined by means of linear equations?” 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 and stable classes, a topic that has been widely investigated in recent years by several authors including Maurice Pouzet.",

keywords = "Boolean function, Clone, Clonoid, Functional equation, Linear definability",

author = "Miguel Couceiro and Erkko Lehtonen",

note = "Funding Information: ⇤This work is funded by National Funds through the FCT – Funda{\c c}{\~a}o para a Ci{\^e}ncia e a Tecnologia, I.P., under the scope of the project UIDB/00297/2020 (Center for Mathematics and Applications). Funding Information: This work is funded by National Funds through the FCT - Funda??o para a Ci?ncia e a Tecnologia, I.P., under the scope of the project UIDB/00297/2020 (Center for Mathematics and Applications). Publisher Copyright: {\textcopyright} 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).; 1st International Conference {"}Algebras, Graphs and Ordered Sets{"}, ALGOS 2020 ; Conference date: 26-08-2020 Through 28-08-2020",

year = "2020",

language = "British English",

volume = "2925",

pages = "21--28",

journal = "CEUR Workshop Proceedings",

issn = "1613-0073",

publisher = "CEUR-WS",

}

TY - JOUR

T1 - Linearly definable classes of boolean functions

AU - Couceiro, Miguel

AU - Lehtonen, Erkko

N1 - Funding Information: ⇤This work is funded by National Funds through the FCT – Fundação para a Ciência e a Tecnologia, I.P., under the scope of the project UIDB/00297/2020 (Center for Mathematics and Applications). Funding Information: This work is funded by National Funds through the FCT - Funda??o para a Ci?ncia e a Tecnologia, I.P., under the scope of the project UIDB/00297/2020 (Center for Mathematics and Applications). Publisher Copyright: © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).

PY - 2020

Y1 - 2020

N2 - In this paper we address the question “How many properties of Boolean functions can be defined by means of linear equations?” 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 and stable classes, a topic that has been widely investigated in recent years by several authors including Maurice Pouzet.

AB - In this paper we address the question “How many properties of Boolean functions can be defined by means of linear equations?” 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 and stable classes, a topic that has been widely investigated in recent years by several authors including Maurice Pouzet.

KW - Boolean function

KW - Clone

KW - Clonoid

KW - Functional equation

KW - Linear definability

UR - http://www.scopus.com/inward/record.url?scp=85113896544&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85113896544

SN - 1613-0073

VL - 2925

SP - 21

EP - 28

JO - CEUR Workshop Proceedings

JF - CEUR Workshop Proceedings

T2 - 1st International Conference "Algebras, Graphs and Ordered Sets", ALGOS 2020

Y2 - 26 August 2020 through 28 August 2020

ER -

Linearly definable classes of boolean functions

Abstract

Keywords

Other files and links

Fingerprint

Cite this