<TITLE: On Definability of Functions of Several Variables
ACADEMIC DOMAIN: natural sciences
DISCIPLINE: mathematics
EVENT TYPE: doctoral defence discussion
FILE ID: UDEFD120
NOTES: continued in and continuation of UDEFP120

RECORDING DURATION: 95 min 3 sec

RECORDING DATE: 16.9.2006

NUMBER OF PARTICIPANTS: circa 30

NUMBER OF SPEAKERS: 3

S1: NATIVE-SPEAKER STATUS: Finnish; ACADEMIC ROLE: senior staff; GENDER: male; AGE: 31-50

S2: NATIVE-SPEAKER STATUS: Portuguese; ACADEMIC ROLE: junior staff; GENDER: male; AGE: 24-30

S3: NATIVE-SPEAKER STATUS: French; ACADEMIC ROLE: senior staff; GENDER: male; AGE: 51-over

SS: several simultaneous speakers>


<S1> <START MISSING> by the faculty of information sciences i declare this discussion open , today master of science <NAME S2> will defend his thesis on definability of functions of several variables the opponent is professor <NAME S3> from the university of claude bernard lyon </S1>

<PRESENTATION UDEFP120 by S2>

<S3> thank you surely , first ladies and gentlemen i'm very honoured to be the opponent in this defence i thank the university and my colleague professor <NAME S1> for offering me this opportunity i thank you for your attention the role of the candidate presentation was to into- introduce what he achieved to indicate some of his advances my duty is first to discuss the position and significance of his research subject presented under this title on definability of function of several variables and to situate it in the mainstream of mathematics , this research subject originate in the study of boolean function as the candidate told you a boolean function is a function with finitely many variables these variable may only have two values zero and one and the function also take only the value zero and one , one could think that that is a very narrow concept and that there is not much behind it , it's totally wrong first boolean function (mimic) propositional calculus connective like (0-N-0) can be viewed as simple boolean functions and since aristoteles the propositional calculus was a basic of logi- logic reasoning nowadays we relies on computers their building blocks are the chips physically realise- realising (some of the) boolean functions , boolean function have also wide variety of applications in data analysis cry- cryptography physical statistic optimisation and so on but what about mathematics , in mathematics the simplest question you could imagine is how to compute the value of a boolean function , that is how to know if there is an assignment of value for which the function takes the value one how to know that , can we do it without trying all the possible assignment of the variable this leads to the following more specific question is it possible to find a polynomial algorithm which when applied to a boolean function tell you if whether there is such an assignment where polynomial means that the duration of the algorithm is bounded by some polynomial in the number of variable say polynomial of degree three no more than N to the power three (xx) , everybody probably in the audience with some mathematical and computer science training will have by now recognised that this is an instance (of) equivalent one of the famous B equal to NB question , which because of practical importance notably cryptography and theoretical one is by now considered by the scientific community as one of the most important mathematical question of our time the simplest question we can imagine on this subject turn to be the most important unsolved question by now , now simple question to state can be extremely hard to solve as every mathematician know , but this question is just the tip of an iceberg , in this iceberg is a research object of the thesis , now if you look at boolean function as (little) devices it is natural to ask if you can build a function by composing the devices that you have in stock if you have plenty of copies of R and N and negation foreign negation for example by composing those device you will get all possible boolean function which is a really striking (fact) yes , now the next thing you will to address is this given the set of device , or you will decide that you get device , what is the procedure to know that with those little tricks i can produce everything here is an answer for you , to set a function you associate the collection of function that you get by composition , yes you give a name the clone generated by this set here is where the notion of clone appear this was coined by the english mathematician philip hall during the 50s for instance a set of all function is a clone alright , next there are maximal clones that is behind the just below there are clones which are different from the largest one for an example is a clone of monotone increasing function now if (for reach) of this maximal clone one of your function is not there then the given set of function will generate everything this was the completude test by emil post but how to decide that a function is or not in your maximal clone in fact there are just five clones and the five clones can be described in term of the notion of preservation presented by the candidate the clone of zero preserving map the clone of one preserving map the linear clone the clone of monotone increa- or not er increasing function and the (xx) function this is a result by emil post in 1920 , since preservation is easy to to get you have a test yes from this basic point post 1920 (xx) theory have have developed since now so i will give you few few point and this will help you to situate the work by erm by the candidate first the description of all clones of the two-element universe emil post 41 and there are only countably many of them the extension to all finite universe a dramatic difference on er finite universe with three element or more there are uncountably many clones and this could explain perhaps some idea why the three-valent logic the K-valent logic is totally different from ordinary logic , still this is a result by <NAME> 59 there is a completude theorem à la post this is a famous theorem by rosenberg 65 1970 there are finitely many maximal clone and rosenberg gives a list of relation of the K element universe (xx) exactly the clone preserving those relation are maximal , yes studies then s- other steps the study of the (xx) notion of clone the algebrisation by <NAME> in 66 the introduction of the notion of preservation by <NAME> the study of the galois correspondence associated with the realisation of preservation which was done first for the two-element universe next for all-finite one geiger bodnarchuk kaluznin kotov romov has mentioned it this was based on the approach by krasner of some special case his abstract galois theory 1939 at that time he was trying to present the ordinary galois theory in a more bit more abstract setting trying to capture the real content he has his endotheory g- endo- er the galois endotheory in 66 now in these result it is said when a set of function on K-element universe is a clone it is also s- which is not a very difficult result but it is said when a set of relation is a set of relation preservation set of function which is a very very deep one later extension sorry those was (holberg's) step later on extension to infinite universe were considered it was a key notion of locally closed clone by <NAME> rosenberg szabo and in some special case by <NAME> and <NAME> further generalisation were considered , starting from the then to formalise er erm formally described set of boolean function closed under only the extended fusion of variable lies a set of threshold function <NAME> <NAME> <NAME> <NAME> in 98 and other found many conditions this was completed by pippenger who introduced this notion of preservation we have heard about , and the with possibly two different universe and pairs of relation , generalisation is not for the sake of generalisation from boolean function we arrive to finally things which can be presented in term of rela- relation and automorphism , these latter object have been studied for years by combinatorialist graph theorist logician it is fascinating to see how nowadays a different approach is invigorative (xx) this is just to indicate that the domain is an active one and it is where the the thesis of the candidate contribute thank you <GETTING SEATED, TRACK CHANGE> so . i will start the examination of the work , er you have introduced your work you introduced and you indicated some (advance) you made you will have now to present your result we will review it i'm asking you first to summarise in concrete term what you have obtained </S3>
<P:05>
<S2> well in this erm , well this doctoral work erm , basically consists of the erm . basically consists of erm these seven papers that that appear in erm in this list </S2>
<S3> okay erm would you please indicate the main theme in which the paper fit </S3>
<S2> well there are basically two themes in erm <MOVING MARKERBOARDS, P:08> there are basically two themes is this er in this doctoral work <WRITES ON MARKERBOARD THROUGHOUT THE WHOLE EVENT> . well er one er deals with equational erm equational , definability of function properties . and also erm explicit equational characterisations <P:06> of erm of some concrete prop- properties <P:07> well this er erm this theme this theme basically comprises the first and the last which are which are referred to as CF-1 , and , CF-5 well the <SIGH> the second theme of , erm , of these papers erm can be described by er definability . by relational constraints . now this erm <COUGH> this approach er was presented in erm was presented in er a galois connection between functions and relational constraints over arbitrary sets and this erm and this was explored in the paper , CF-3 <S3> yeah </S3> well this <COUGH> from this study erm or this study was refined and and specialised er in the , erm . this this constitutes CF-3 and <P:07> and erm yes it was it was refined and special- and specialised <P:08> in , C-1 , well it was er it was extended erm to multi- to the multivalent case . in the m- in the mu- for for multivalent functions in C-2 , and it was refined erm in the paper in the joint paper with <NAME> which is er which is referred to as CF-4 <P:10> well in fact the the results presented in erm or this this paper generalises the the results which were presented in in CF- CF-2 </S2>
<S3> CF-2 okay yeah <P:10> yes any other special other comment to make </S3>
<S2> well yes er erm the paper CF-1 or the ideas er presented in the in the in in this paper CF-5 or this paper CF-5 can be seen as a generalisation of of C- CF-1 for example the the the final erm characterisation that i that i gave in in my slides er well this er this result had already been considered erm in CF-1 in the particular the particular case of er boolean functions </S2>
<S3> let us look at CF-1 please so what is er (what would you like) to give to the audience the special form of the result , <ORGANISING PAPERS> er yeah , yes . sorry there you go </S3>
<S2> well this this result was presented in , can i er can i now <SWITCHES OFF THE OVERHEAD PROJECTOR> </S2>
<S3> yeah yeah yeah yeah of course </S3>
<S2> this th- this result characterises the erm , the classes er of boolean functions which can be defined by means of equations and it can be stated as follows . er for for any . class er . of boolean functions er plus let's call it K we have that the following are (equipment) <P:16> er first erm the , the statement says that K is . linearly . definable that is that K is definable by means of linear equations , the second statement says that K is definable <P:05> by affine constraints . and the condition erm er the condition characterises the classes er the classes or the linearly definable classes and the classes definable by constraint was presented in terms of of generators of the , of the clone of constant-preserving linear functions er and this clone is generated by by the triple sum by the boolean triple sum and the condition was even as follows so K is . is closed , under substituted . erm triple sums of variables , for variables . and er the condition the external condition tells us that K is erm closed under . formation of triple sums of functions . of course the functions (of the same kind) </S2>
<S3> okay this is a general result but er but give an example so so erm can you deduce from this a typical example of [definable classes] </S3>
<S2> [well] well as i i have shown in my in my presentation the the clone of er constant er of linear functions er is definable by <S3> yeah </S3> by linear equations or but there are several other actually there are infinitely many er of such classes er linearly definable classes for example if we if for e- for each positive integer . the class which are going to be (multiplied) (xx) functions which have er polynomial degree bounded by by M er constitutes an example of er of a class of definable variables </S2>
<S3> okay well erm to a naive what is the significant part of this thing </S3>
<S2> okay the most difficult part and that i find most significant is to show that if a class satisfies these conditions then it is linearly definable , this for me is the most </S2>
<S3> yes did you develop on that </S3>
<S2> well to to prove to to prove that er the third condition implies the first one <S3> yeah </S3> erm we used as tools erm constraints so <COUGH> , so first we we we showed that classes satisfying these conditions are definable by means of affine constraints and then we showed that these classes erm well f- the the trick was to show that er for each of of of such set of of of for each er such affine constraint we can construct er linear equations which which are defined exactly (the s- or satisfy these) </S2>
<S3> surely but can you be more explicit </S3>
<S2> erm yes so maybe if you <S3> yeah </S3> <MOVING MARKERBOARDS, P:13> well to first to to show the first implication that is that the third condition implies implies the erm the second well we first noticed that these conditions subs- these conditions subsume closure and the simple variable substitution and this tell us that erm the class , the class satisfies . er the third condition then this class , is . definable by , by constraints because the third condition and there is a step missing here </S2>
<S3> yes how you (xx) how you guess for your affine constraint </S3>
<S2> well to mhm </S2>
<S3> you know your class satisfies this </S3>
<S2> [yes and this constraint is really] </S2>
<S3> [er this condition and you] have to invent to imagine some constraint [yes] </S3>
<S2> [yes] well the first <COUGH> the first part of the the third condition er closure and the substituting erm triple sums of variables for variables well implies that erm , well let's say that it's a set erm by a a set T of constraints <P:06> er of constraints so the the erm maybe i will call it . A and B erm well the condition A er implies that this set of constraints can be replaced by a set of constraints in which the antecedent is closed under triple sum so we can substitute <P:14> <S3> yes [sure yes] </S3> [by constraints] . erm with antecedent <S3> yes sure </S3> (xx) triple sum , (xx) </S2>
<S3> but still you have to find a key , you are showing us that if it is closed then you are substituting things yes <S2> mhm-hm </S2> you are able to find constraint <S2> mhm-hm </S2> so (xx) result how you guess which type w- which which constraint are </S3>
<S2> this er , do you want me to expose yes okay </S2>
<S3> [(the idea is)] </S3>
<S2> [so yes] the the the proof is basically the proof er given by by pippenger <S3> yes </S3> , so <SIGH> well we have erm . we have er a class K <S3> yes </S3> which is assumed to be by pippenger's case which is assumed to be closed under under simple variable substitutions , and then we look at er a function which is not <S3> [yes] </S3> [(integral)] so what we do is erm that we can w- we construct erm a constraint <S3> yes  </S3> which <S3> separate </S3> which will separate exactly which will separate the function not not in the class <S3> yeah </S3> and to construct this erm this constraint let's suppose that erm this is erm the G er this is a , N-ary . function <S3> yes </S3> , so we define a a relation R . which is erm , which can be defined by the erm <P:05> by the (xx) <P:08> i will explain what i mean by <P:08> so we define a sorry <MOVING MARKERBOARDS, P:10> <S3> yes </S3> we define a a relation R which comprises er the . the two N- er tuples erm the the the two N-tuples such that if we look at mhm so if i if i if i represent these tuples as follows , if i look at erm at each coordinate of this of these tuples then this set of erm well so to speak we have a matrix and <S3> [yeah] </S3> [this set] and this set of rows erm constitutes the whole (VN) so that is to say that this constitutes the whole domain of the function that we want to separate <S3> yeah </S3> from the from the set K so then what we do to construct er the relation S what we do is that we look at </S2>
<S3> oh i'm sorry </S3>
<S2> we look at all functions er , all N-ary functions er belonging to K and we define S as . (in the union of) (xx) of all these these functions </S2>
<S3> so okay so i want just to point to point that it's a (separated) property <S2> yes </S2> and perhaps this explain why pippenger was using the term constraint <S2> yes </S2> it came from a (xx) and et cetera okay thank you so now what about the second (plan) </S3>
<S2> so i do not continue with the well if you wanted to say that the the B er condition erm guarantees that we can substitute this the this er set T (plan) by a set in which er also the consequence are closed under triple sums and in the boolean case in the two element field this this condition is just the same er same that these constraints are affine so indeed from from these two conditions we can we can guarantee the existence of such a set a defining set of (xx) <S3> okay </S3> okay okay so <P:10> well to show . that two implies one well we made er use of some basic facts of erm linear algebra well the first fact , which tell us that , every affine . subspace is the range . of erm . affine transformation . and the second fact . which tells us that every affine subspace is the solution set <P:05> is a solution erm set for the system <S3> okay </S3> of the equation . i'm using the the maps of the affine forms given by fact by this fact and this we were capable of constructing the the inner and outer expressions of er functional equations </S2>
<S3> okay okay this is over GF-2 so what over GFK </S3>
<S2> well these type of operations over GFK were actually considered in erm in the last section of of the thesis er which which contains some published materials erm and that actually in that in that section we considered a little bit more general functions functions which are defined over , over er a a finite er finite field and valued in in a possibly different finite [field] </S2>
<S3> [uh-huh] yeah okay yes . yes and </S3>
<S2> well er in this case the result is is basically i- it's er basically the same but th- th- the condition was given , was given in terms of erm , was given in terms of class composition instead of in terms of erm of clo- or composi- stability in the composition with clones instead of erm </S2>
<S3> you know here we see tree we're seeing tree we could immediately ask ourself if we put K GFQ or or or it will go but you don't present the result that way alright </S3>
<S2> yes we present basically as i as i given in <S3> i see </S3> in the </S2>
<S3> and why is that wha- what did we tell in GF-3 for example just basic question GF-3 </S3>
<S2> well in this case if we want to provide the conditions in the same then we have to substitute the generating function which in GF-3 could be given by of course here addition and er <S3> [i see] </S3> [the] this er addition <S3> [yeah] </S3> [(inverse)] is given in GF-3 </S2>
<S3> okay thank you , thank you so your first part was about GF this one and the the CF-5 let us go to CF-5 and er please first what is the content of the paper </S3>
<S2> well in this erm in this er in this paper we basically er or as a consequent we deal with erm , we deal with er er equational definability for erm field-valued functions with boolean er variables so these type of functions including in in in in particular boolean functions er the so-called pseudo-boolean functions which are functions er defined on on erm on er on the two-element set and and valued on on the real numbers <S3> yes </S3> well we <COUGH> we well in this paper we showed that or we we considered first erm particular cases of erm of of these functions so the particular classes we we- we were interested in this er bounded-degree erm classes well and we we showed that each of these classes can be defined by means of of equations and er we gave also a characterisation of the linearly definable classes but er in this paper it was given erm in terms of the the characteristic of the underlying field <S3> okay </S3> the the the (xx) so we well in this well with this we we also presented several equational characterisations for this type of for for this particular type of classes er according to er whether they are er linearly defined so the the the equations were either linear or non-linear according to our characterisation and and this for example answers the one open question in the first paper in CF-1 er well in this paper we had already pointed out that that these classes of polynomial bounded polynomial degree were definable by means of linear equations <S3> yes </S3> but we didn't present er the concrete equational characterisations of [(these classes)] </S2>
<S3> [yeah] okay so in this paper you have concrete examples that you are studying right <S2> yes </S2> and so but y- there are also general reasons <S2>  yes </S2> so , on which the proof is based yes so would you like to present them </S3>
<S2> well first we started by erm , can i <S3> yeah </S3> maybe i use the parts er <WIPING THE MARKERBOARD, P:08> so maybe w- er first we we we sta- we started by establishing a complete correspondence between equations and relational constraints in the sense that er definability of the the classes which are definable by means of equations are exactly the same as those defined by means of relational constraints so , the theorem is , equational definability is equivalent to er definability by , by constraints , well the proof of this result revealed general criteria to kind of strengthen this connection between equations and relational constraints in particular we show that linear definability , is again er equivalent to definability , by affine constraints and for example for the for the the characterisation of those o- of erm which classes which er of these classes erm can be defined by means of linear equations er , well we had to use results that actually w- were presented in already presented in C-4 so we made use of this correspondence <S3>  okay </S3> and this (take us to to the second part) </S2>
<S3> yes okay wh- wh- wh- where is the where is the crucial part in the first theorem </S3>
<S2> which in this [one] <S3> [yes] yeah yeah </S3> mhm . well the crucial step is to , well first of all we yes but maybe the crucial step is to show that definability by constraints is given by [(xx)] </S2>
<S3> [you you er] (you are able to do) the equation yeah <S2> yeah </S2> yeah okay </S3>
<S2> this was again by using the fact that each (equation) can er appears as the range of of er a given (mapping) on on <S3> [yes yes] </S3> [this type of transformation] and each each set can be expressed by a [characteristic function] </S2>
<S3> [yeah yeah] yeah so could we say that this will be a bit clearer by going to to to part B <S2> yes </S2> yes okay so please let us go to part B and er so since you have this approach perhaps introduce the motivation for the galois framework </S3>
<S2> in CF-3 <S3> yes </S3> well erm , as we have seen constraints er appear as tools or we use constraints <S3> [yeah yeah] </S3> [a- as a tool] to attack questions <S3> yeah </S3> er of equational definability of classes so erm well these facts kind of erm draw attention to to to pippenger's framework well th- pippenger's framework only deals with erm with functions with finite functions functions over <S3> yeah </S3> finite sets so the the first question is er how to <S3> extend </S3> yes how to <S3> [yes] </S3> [extend] this this framework to the to the general case </S2>
<S3> yeah okay so what you did then </S3>
<S2> well er mhm , the i'm sorry i i don't [er] </S2>
<S3> [so] describe to us the contain of CF-3 </S3>
<S2> well this the CF-3 contains the description in particular it contains the description of the of both closure systems u- used by this galois connection between functions and relational constraints well the the characterisation of functions well it's basically the same it's again by using the the local closure that we obtained <COUGH> such a characterisation </S2>
<S3> and it is not much substantial right <S2> no </S2> yes yes </S3>
<S2> like local closure just guarantees the existence </S2>
<S3> it's nice but there is not much substance <S2> yes </S2> okay </S3>
<S2> yes the the second part the characterisation of the dual closure systems were in the </S2>
<S3> so so now (xx) substantial it's time to go to go to the core </S3>
<S2> shall i actually erm i have some slides that i would like to maybe introduce the , okay so i'm going to start by i have spoken about erm to the audience <S3> okay </S3> i have spoken about the the the closure conditions er describing the the sets of relational constraints erm involve the combination of families of relational constraints into new constraints by means of er possibly infinitary formal screams schemes and also it i- it erm it involves er a notion of of erm of local closure and and i will try to in few slides try to to present erm these these closures try to <S3> [yes] </S3> [explain] these closures <ORGANISING SLIDES, P:19> <COUGH> okay so first we . we we define what we mean by these formula schemes well these formula schemes are basically er <MOVING MARKERBOARDS> . these formula schemes are <COUGH> are simply positive primitive er formulas which er which have er finitely many free variables but which appear in the fragment of in an extension of er of versatile logic which are written in a possibly infinitary language er so that is to say that mhm this formula is the existential (configuration) er over er a conjunction but both the erm the existential (configurations) and er the conjunctions may be er infinite . well now each of these expressions can be each of these expressions can be gives raise to to a relation erm so fo- for each relational structure of the same er signature of the the formula scheme er these formula schemes can be interpreted in these relational structures er in a natural way as the set of realisations or erm of the the the formula the formula scheme and this is done by interpreted er each er predicate symbol er by the corresponding er relation of of er the same type , now we say that erm we say that a a given A to B relational constraint RS is a conjunctive minor of a family of relational constraints indexed erm by a possibly infinite er infinite set of indices er if there is such a formula scheme er which defines relations on A and on B erm such that erm this relational constraint is a relaxation of this pair so basically it's it's this that is the the antecedent is containing the relation erm defined by the formula scheme in the structure A and erm and the S is an extension of the the erm of the the the relation defined on B er defined by means of the formula scheme on on the structure B <SWITCHING SLIDES> . so in this . so now we say that erm we say that the set of relational constraints is closed under formation of conjunctive minors if this set will contai- contains all relational constraints which can be obtained in this form that is all conjunctive minors of non-empty families of its members , now the loca- the notion of local closure is defined as follows so we say that a a set B of relational constraints is locally closed if it will contain erm every constraint whose set of relaxations with finite antecedents are all in T so er that is to say that if a constraint is not in a in a set T of of relations then we know that there will be erm a relaxation of this relation with a finite erm antecedent which is also not not in the set T now using this erm these two conditions closure and the formation of conjunctive minors and er local closure we have shown that erm a set of relational constraints erm is definable or specified by means of er a set of functions or class of functions if it is locally closed and of course contains the erm the the identity constraint and it contains the empty constraint because these constraints are satisfied by any by by every function and it is closed under formation of conjunctive minors so this is the characterisation of the the dual erm closed sets of relational constraints </S2>
<S3> okay well you present something which is very clean but which is an end of the process and if somebody's not an expert he will not grasp this construction because it's a very general abstract thing and and with concrete example maybe we can realise what is this exp- what is the meaning of this scheme <S2> mhm-hm </S2> so you have some relation you associate the construct with new relation could you give some example of things that we get by this this way </S3>
<S2> that we can get </S2>
<S3> because you don't discover that on the morning with such a definition yes <S2> mhm-hm </S2> this is the end of the pre- process that you present fini- er the product is fin- er er finished it's clean <S2> yes </S2> but you don't show how it works <S2> [mhm] </S2> [could] you try to explain </S3>
<S2> this er this closure and er yes </S2>
<S3> give example just example of construction <S2> mhm-hm </S2> of constraint starting with some </S3>
<S2> <WIPING MARKERBOARD, P:07> so can i give you the finite (in this case) <S3> [oh yeah] </S3> [just two] two relations <S3> oh yes </S3> <MOVING MARKERBOARDS> (xx) . for example let's consider , the relation R-1 which simply comprises er , let's say let's say that this we we are playing over the natural numbers <S3>  yes </S3> one two three and so forth so this this relation comprises er the tuples one and two and erm <P:05> let's say three four just these these two tuples er [they are] </S2>
<S3> [it's pairs] </S3>
<S2> sorry they're pairs yes <S3> mhm-hm </S3> it's a binary relation <P:10> er let's consider the relation R-2 containing <P:05> let's say , two three <S3> mhm-hm </S3> , and let's consider a formula scheme for example erm <S3> [yeah] </S3> [which tells us] by the way this symbol mhm i i don't know if the the audience is familiar with this er notation but i will try to explain it </S2>
<S3> concrete example </S3>
<S2> yes how how do i er erm <P:06> this is X this would be Y and (xx) <P:06> and this would be er (xx) . so now we look at the , well here i i used the the relational symbols in the same way <S3> [yes okay] </S3> [(xx)] (xx) now if you interpreted this <COUGH> this erm this expression is formal expression , in the natural numbers er and our struct- our relational structure contains both of these relations , R-2 now if we look at er . well here the the the free variables of this formula scheme are the because they are not bounded erm . (xx) <S3> yes </S3> okay so there are two erm er free variables the only variable that is bounded by the existential (configuration) it simply s- means that there is Z such that erm YZ YZ belongs to R-1 and ZV or ZX belongs to R-2 so this <COUGH> this formula scheme that has Y and X as free variables seem to be , seem well as we see the only the only possibility is for the Y to be to have the value one and the the X to have (different force) and this simply defines the relation which contains the tuples , which contains the unique tuple (xx) </S2>
<S3> in other words you are er you are expressing the composition right <S2>  yes </S2> you could have perhaps given another example because you would not have i- you would not have invented s- so huge machinery (xx) right <S2> no </S2> okay okay okay erm could you i know that this is one of the substance in your work but could you comment on it on this theory </S3>
<S2> <SIGH> on the the proof <S3> yeah [@@] </S3> [well the erm] yes this is was actually one of er it's one of our favourite er was one of our favourite er proofs anyway so the <COUGH> the strategy to well first of all the erm the easy part of this proof is to show that two implies one , so to show that if er a set T of relational constraints is characterised by a function class then it must be locally closed it must so the the the hard part of the proof the really hard part is really to show that one implies one that is the set of [relational constraints] </S2>
<S3> [constraints] yes yes </S3>
<S2> if the set of relational constraints satisfies the condition in one then it is definable by means of er some function class well and this strategy to <COUGH> to show this implication erm was the same used by er er use- used by geiger and also by by pippenger erm to characterise the dual er closed set that is to say and which was exactly the the idea is exactly the same as that er presented for er for the description of the primal objects so we start with erm so we assume that we have a a set T of er relational constraints which satisfies the conditions <S3> yeah  </S3> and now for each relational constraint outside this class what we do is we try to construct again a separating rela- er a relation RS er er function sorry and er @this is really not good@ er functions er f- the er function which which separates this er separates this constraint let's call it RS from the the closed set of relational constraints and when i say that it separates it means that er this function satisfies every every relational constraint in the set T and but it fails to satisfy this erm this relational constraint so the set of all these functions which i even index by the relational constraint , the set of of each of these functions for each relation constraint not in our in our closed set T erm will constitute so to speak in so will define will constitute the defining set of erm of functions , well but erm maybe the nice- the nicest thing of in our proof er was that erm well geiger and pippenger er constructed such such er such functions such se- separating functions by starting with a partial function and then er extending <S3> [yeah] </S3> [it] pointwi- pointwise extensions to a total function <S3> yeah </S3> well in our case er we didn't we didn't follow this er this approach we didn't even though we tried to use some kind of er induction (xx) <S3> yeah </S3> so we we we we did not follow this we we couldn't we weren't capable to follow the same the same line of thought so what we did was to define at once a total function which separates the two <S3> ah </S3> and the trick here was to consider er well extend this set of infi- of finitary er relational constraints by means of conditions er of erm well extending this set to infinitary constraints basically so we construct a . a larger set of of er relational constraints by means of er well natural extensions er of these conditions to the infinitary infinitary case that is to say that the formula schemes that now we consider they are allowed to have i- infinitely many er free variables <S3> oh yeah [okay] </S3> [yes] and it turned out or so so the the steps were to to first consider this larger se- set well of course showing that er this smaller set is just a restriction of this larger set to finitary relational constraints <S3> mhm-hm </S3> , and then in this in this larger set we were capable to <S3> (find it or) </S3> yes to to to obtain er to to to kind of define er relational constraints in which the antecedent would er basically gather all all the the tuples in the domain of the function and this allow us to to construct a total function at once </S2>
<S3> yeah , yeah so so this is new so this is a new approach </S3>
<S2> yes er w- well that proof it is the the proof of the erm of the primal objects is is er but it's basically just the (original) type of of closure and the steps of the proof are exactly the same this is a totally new approach </S2>
<S3> okay according to your terminology primal-dual have you been looking at convex analysis er er yeah because separ- separating plane er (xx) ha- have you been looking at that because th- there is a same thing which happen [(xx)] </S3>
<S2> [(xx)] if you want to define er the use er [(xx)] </S2>
<S3> [yes (xx)] and things have you been have you been try to at least to establish a catalogue </S3>
<S2> mhm not yet <S3> okay </S3> but yes i i i i i am aware of the i am aware of the (xx) convex <S3> yeah </S3> convex [(xx) interesting] </S2>
<S3> [okay thank you] okay this is about i think the CF-3 <S2> yes </S2> or we could go to C-1 </S3>
<S2> C-1 , mhm so to more or less er describe it [or] </S2>
<S3> [yes] yes @because@ <S2> okay er </S2> (we're looking) through </S3>
<S2> so i say er <SWITCHES OFF THE OVERHEAD PROJECTOR> if you don't mind , that i say here that erm this basic galois connection between functions and and constraints is refined and specialised in C-1 <S3> yes  </S3> so what why do i say that it's erm it's further refined well because in in in in CF-3 er we presented er the necessary and sufficient conditions on the on to describe the the closed sets <S3> yes </S3> sets <DISC CHANGE> for example for unfunction classes it tells us this er closure operator is dec- is factorised as the composition of LO which stands for local closure , and and VS which stands for closure in the simple variable substitutions and for example for this case it's , erm it is factorised er as follows well moreover i use the term here er specialised in C-1 because this wasn't the the only the only galois connection that we considered er by restricting both sets of classes of functions and sets of relation- relational constraints to er fixed additives like this restriction er induces further galois connections so for each for each positive integer N and positive integer M the restriction of er function classes to N-ary functions and the restriction of er <S3> [okay i see] </S3> [sets of relational constraints to N-ary functions] so what we did was to describe each one of these of of these new galois connections which are obtained from the previous by by restricting the sets of of erm <S3>  yeah </S3> functions of the (xx) </S2>
<S3> so in any case you prove that if C is a (basic) function then the closure consists first to take the closure of the variable substitution a- and then to take the local closure right </S3>
<S2> no because to first take so first apply the local closure i'm sorry </S2>
<S3> isn't it ex- exactly that i said </S3>
<S2> i i i didn't understood i didn't understand i'm sorry </S2>
<S3> variable substitution and then you apply local closure in that sense </S3>
<S2> yes yes yes i'm sorry i i i'm sorry </S2>
<S3> okay why is in this order <S2> well erm </S2> okay yes because it is true but [@@] <S2> [mhm] @yes@ </S2> could you permute those two things </S3>
<S2> mhm these two operators cannot be cannot be commuted they do not define all the okay in in this thesis we show that for example if a if a class is locally closed , <S3> yeah </S3> then indeed these two operators commute but in the general case if we don't have this assumption <S3> yeah </S3> in the general case it's not it's not true </S2>
<S3> it's not true why </S3>
<S2> well the the proof is given by the the proof will be given by a counterexample <S3> okay </S3> so we want to show that , it's not always the case , this goes (xx) there , this does not happen for every for every class K well and the example that i i i i constructed erm i take a class K <S3> yeah </S3> which erm which consists of a family of functions inde- in- indexed er by natural numbers and this this class er is defined also in natural numbers <S3> yeah </S3> it was the the main (xx) so this is the the class <P:08> and for each N er this function is defined as follows , for each N er the function in- indexed by N is an N-ary function <S3> mhm </S3> . and the value of this function is A if <P:07> if all the entries of the of the tuple are the same er point A and if A belongs to to a kind of (xx) . otherwise this function will assume the value the value zero , now as immediate consequence of this of this definition we see that for each er positive integer we have exactly one function o- with that arity <S3> yes </S3> this tell us that local closure is (xx) satisfied so that is to say that VS LO of K is just equal to VS of K <S3> yeah  </S3> , now let us consider the erm , the unary and the the identity function that is the function that takes each natural number to to itself , now this this erm this function let me denote it by an I , this function is not containing the variable substitutions <S3> yeah </S3> because each of these functions is basically a (xx) function on finite subsets but let us look at , i can't <WIPING MARKERBOARD> i hope that the audience is following i know it's messy with my <P:09> now , this function belongs to . LO VS of K why is this so well because we can consider erm all functions which are obtained from this family by identifying all all of the components <S3> yes </S3> and then we obtain a family of functions which will have which is defined as follows so a func- er G function of unary functions . this N-ary belongs to one , N and it's zero otherwise <S3> mhm-hm </S3> now this function is in the closure and the simple variable substitutions but now as we can see here for every finite restriction of this function you can find one of such functions that so in the the identity belongs <S3> yeah yeah yeah </S3> now but this identity function is it's easy to see that we need it in the <S3> [yeah] </S3> [local closure] to guarantee that the function . that er this identity function belongs to this er closure and to the [simple variable substitution] </S2>
<S3> [yeah (the two)] it's a nice theorem to say that you start first with with variable substitution then you take the local closure and it's a nice observation that you cannot commute that so why this this is not there </S3>
<S2> it is it is true <S3> yeah </S3> if i could go a bit back [because i would have] </S2>
<S3> [@@] yes okay thank you so let us go to this er final thing CF-4 </S3>
<S2> CF-4 </S2>
<S3> yeah will you please say some words <S2> [because i-] </S2> [about CF-4] because there is some contents there </S3>
<S2> well CF-4 the motivation for for er in this maybe i speak of the motivations [of the paper] </S2>
<S3> [yes that's] please </S3>
<S2> okay so the erm the motivations of this paper was that we wanted to construct a galois framework but looking at our our description of the equational definable classes we see that erm these conditions are given in terms of stability under certain composition with clones <S3> yes </S3> so this paper appeared to er we wanted with this paper to be able to describe or to kind of capture this notion of stability erm of function classes and this er this this was achieved by considering by considering erm constraints , where the antecedent so for each pair of to capture a class satisfying the condition . that is that is stable under right composition and stable under left composition we considered as defining objects relational constraints but , assuming that the antecedent and consequent is are invariant under the clone C-1 <S3> yes </S3> and and C-2 but so so this is to say that for each pair of clones C-1 and C-2 we obtain a new galois connection in which function classes are <S3> [yes] </S3> [defined] by means of C-1 C-2 <S3> [yes] </S3> [constraints] and and er sets of C-1 C-2 constraints are defined by means of functions so and and indeed we we we achieved our we we achieved we reached @our@ our goal our our our initial goal because it turned out , that the classes which can be defined in this setting are exactly the classes satisfying the con- er the stability condition , <S3> yeah </S3> and these are exactly the the classes defined in the , so these two conditions are the are the equivalent , erm C-1 C-2 constraints <S3> yes  </S3> . and we also considered the the dual question of which sets of these type of constraints are <S3> yes </S3> and it turned out that basically the description of this set of erm , of this erm well the dual question of which sets of relational constraints can be defined by functions turn out to be basically the the the restriction of of the closure conditions that we give here er two sets of relational constraints containing only those type of of constraints this was basically the the proof wasn't so so easy but and it's a bit tec- technical </S2>
<S3> yes so could we say that the novelty here is in the approach of considering a pair of clones </S3>
<S2> yes the [(dual)] </S2>
<S3> [for for] cor- for the constraint yeah <S2> y- yes </S2> b- er by by taking those C-1 and C-2 </S3>
<S2> to be clones <S3> yes yes </S3> well this this in fact generalises several <S3> yes yeah </S3> several other works like also already pippenger had considered some kind of stability and the clones of utmost unary functions <S3> yes </S3> and erm and the description was given by by constraints in which the antecedent he called it saturated but it means that the antecedent is invariant under the clone of utmost unary well this also generalises the erm strengths and the the o- or includes the the CF-3 because if we take C-1 and C-2 to be clones of of projections then we are in the basic case and well in some sense it also it also subsumes the linearly definable classes because if we if we take here the clones of constant-preserving linear operations then we are exactly in the same in the same in the same framework </S2>
<S3> okay alright so for you w- what is the essential content of this part B </S3>
<S2> this part B </S2>
<S3> you have presented this but you have also presented the the CF-3 in your view own view what do you consider </S3>
<S2> well as </S2>
<S3> the things and the n- not [necessarily] </S3>
<S2> [achievements] <S3> yes yeah </S3> erm well a- as achievements i you know e- even though <SIGH> i don't know i like this proof <S3> okay yeah </S3> because we in some sense we we got distant from the <S3> yes </S3> the common approach which is to <S3> okay </S3> let's construct piece by piece so here it was well it was a different it was a different method </S2>
<S3> thank you have you any other comment to make on the </S3>
<S2> mhm i i i just would like to say that you know even though erm we haven't still explored all the all the potentialities so to speak of this framework i like a lot the idea underneath erm this CF-4 <S3> okay </S3> or the actually this er this er this motivated basically or it was there in the starting point of our joint research which was to kind of obtain er a general correspondence between the syntax of equations and erm invariants we thought that we could express that by means of </S2>
<S3> mhm and is so this was the original goal </S3>
<S2> mhm this was actually the first time that er <S2> i see </S2> there's something in these lines </S2>
<S3> have you any other comment to make on the over the the thesis </S3>
<S2> mhm i @mhm@ okay i haven't still i haven't presented any any of the equational characterisations and well the equational characterisations are are they are specifically concrete <S3> yeah </S3> but i , i like it a lot maybe it's erm as result it's not very interesting for the the whole community but i have to confess that the quest for these er equations is er is and it's all the time coming you think about something and you try to characterise and check mhm is this yes <S3> yes </S3> then you try to find the equa- and this is er it's quite it was quite (an explosion) </S2>
<S3> yeah thank you er so for me this ends the examination of the content the real content of the thesis but before before i will ask you another question so you have presented several results right <S2> mhm-hm </S2> er but people want to to capture what a person has been contributing (in very few short sentences) so what is the the thing (you realised so the ending in general terms you would like) to remember what you are doing there <S2> mhm </S2> i know it's a difficult question but everybody face that question </S3>
<S2> well i would like people to remember that erm , mhm , well <S3> [that one] </S3> [first this] @technique@ yeah i- no it's one of the the things of course i am interested in that people also keep in their minds that i er together with <NAME> we tried to <S3> okay </S3> to establish er maybe this gives ideas for [(xx)] </S2>
<S3> [so you were er] you were lucky to find another one <S2> mhm </S2> okay now sorry but i'm curious about something else you presented a thesis but you are a mathematician and as mathematician don't stop to his thesis this thesis is already in the past i would like that shortly you would expose what you did after what you intend to do project are just project but you did thing after and if you could give a short brief overview this will help people to realise where you are going <S2> [mhm-hm] </S2> [and] when we know the goal we see the projectory </S3>
<S2> <BEGIN PREPARING OVERHEAD> yes so yes , yes i brought some , i also brought some slides erm containing , er my publication lists not appearing in this in this er . in this thesis </S2>
<S3> is it no well </S3>
<S2> maybe if i can use those <P:07> <FINISH PREPARING OVERHEAD> and you want me to say a few words on them yes </S2>
<S3> very shortly , <S2> [well er] </S2> [and and] then you have to think some- something that people could remember </S3>
<S2> well in the erm in the first <COUGH> i- well the first is just a survey paper on equational definability of er boolean function classes , well on the second erm C-3 erm well we we looked at the erm at the set of all equational classes of operations er over a given set A er now this erm this set er constitutes a lattice under union and intersection but even in the the most basic case the the case of er boolean functions er this lattice is is uncountable erm so what we <SIGH> and thus the description of this lattice is <S3> yeah impossible </S3> you can forget about it <SS> @@ </SS> so we we tried to give a better understanding of this lattice by looking at these closed intervals and when i say closed intervals i'm saying that <WIPING MARKERBOARD> , so the . so maybe i could use the because i brought post-lattice and it's always a nice diagram if you don't mind <S3> yes </S3> <ORGANISING SLIDES> . so erm this , this this er this picture erm er this diagram basically pictures erm the the lattice of all boolean clones er which was er was classification and was obtained by by </S2>
<S3> [post 41] </S3>
<S2> [post yes] yes and as we see it's a countable lattice of course for er and the line sets greater than than two , nobody knows , people know more or less the ma- erm or they know the maximum they know the the minimum of some cases and erm okay thi- this is the the cl- the classification here when we when we have segments er these segments just represent the covering relation between clones that is it just says that between this clone which is by the way the clone of conjunctions with the erm with the with the constant one er and the the clone which contains only the identity of projections and er the constant one there is no clone in between so this represents the covering erm relation , so what we did is that okay our lattice is er is uncountable what can we say about this so what we looked was that intervals in this in so this kind of gave us the frame er for analysing the lat- the the uncountable lattice of equational classes so we look at all the equational classes that appear in between any two here there anywhere so we look at er at these at these which we call closed intervals which by the way constitute a a semi-group under class composition erm and we presented a complete classification er for all pairs of of clones er in terms of the size of the the interval that they they generate and er maybe the the nicest erm or one of the main results of this of this work was the characterisation or the classification of each of these intervals in terms of a condition which generalises associativity for N-ary operations <S3> okay </S3> er and which by the way was already studied by post in the spirit of the so-called M-groups so and and this condition i- is nice and well we arrive maybe i still speak er about some some connections that may exist but anyways okay so erm <ORGANISING SLIDES> (do i put back) . so in the <COUGH> in the CFL er one erm which was a joint work with er <NAME> and <NAME> both are are here well in this <COUGH> in this first work we we simply erm observed that erm er classical normal form representations of boolean functions can be expressed erm because be expressed in terms of class composition erm so for a just for a quick example <S3> quickly quickly </S3> erm , well the er normal form representation er theorems like for example the CNF erm so the the conjunctive normal form representation of boolean functions can be restated as er the factorisation of the clone omega of all boolean clones as the composition of er the conjunctive clone that is the clone which contains conjun- conjunctions the disjunctive clone and , the clone i star which denotes er variables and negated (xx) erm so in this paper we we observed that er there is this (xx) or there is this way of restating these normal forms so this erm this motivated erm our next work er in which we stuvy- studied the composition the class composition of clones and we presented a complete classification of all pairs of clones erm whose composition is a clone and whose composition is not a clone and erm well this this er as a as a consequent we obtained all factorisations of the maximal clone into minimal clones er that is er and these factorisations correspond to normal form of representations so this this study revealed the the existence of a new normal form er which we call median normal form since erm it's based on on a unique er operation which is not N-ary which is the median operatio- ternary median operation and we we presented a comparative er study of of this er with the erm with the more classical normal forms and we showed that er the median normal form is erm or erm is more efficient than the more classical notion since it provides erm expressions of er of lower complexity that is er shorter er expressions well these these results <COUGH> were then applied to mhm in a geometric framework er in which erm sets of er of vertices of an N- N-dimensional Q erm were represented er in terms of convex sets by means of union er symmetric difference and and the ternary median operation well and the next er then put this in erm in a joint paper together with er <NAME> and also , er <NAME> @@ with <NAME> well we investigated the we investigated connections between erm equational definability of boolean function classes and erm definability of erm of frames in in monologic erm well axiomatised by erm well frames and monologic er from this from this work we we we obtain a general erm a general correspondence between erm a er equational classes of boolean functions and erm classes of of frames which are axiomatisable by model formulas of er a given er prescribed syntax and this er this correspondence er was obtained by means of er a really s- er well simple translations between er equational between erm equations er functional equations and erm this type this particular type of model expressions and moreover we we refined these results to to to mhm correspondences between clones and the so-called er (xx) frames and then er well and then in the in the final papers well we erm well the motivations for for these papers are found in a in a work er by <NAME> <NAME> <NAME> and <NAME> and in this work they erm they completely described er equational classes of boolean functions in terms of a quasi-ordering and well the quasi-ordering is a following , so we say that a function G is er to make it simple minor of a function F if and only if G composed with er G composed with the the clone of projections which is in the boolean cases denoted by IC is contained in the composition of of the function F with the erm , with the same er clone of projections well in in that paper erm they characterised erm equational classes in in two ways well equational classes were characterised as initial segments for this erm for this quasi-ordering that is sets which contain every function , er such that and the A is the same (mutation) , such that there exists an F in the class which is (aborted) so it contains <P:09> well they they were er represented as erm th- they were described as initial segments that is to say that the class must contain every function below the functions in the class but they were also characterised in in terms of erm minimal obstructions that is as complements of final segments whoops , final segments which are generated by antichains so basically it's this so what we we did in this in this joint work er with <NAME S3> was to mhm was to give a better understanding of this quasi-ordered set which i'm going to denote use the (xx) (denotation) this er this quasi-order- this quasi-ordered set erm well by by presenting er some properties of the partially ordered sets er associated with this er quasi-ordered the partially ordered set of equivalent classes well one of the main results in er in the first was to mhm was to provide a characterisation of of this erm of this partially ordered set of equivalent classes of boolean functions which er by establishing er equimorphic relation with the set of all finite subsets of erm of integers and moreover in in each of these papers we presented several er characterisations well both in terms of equations by means of explision- er explicit equations and also by providing erm by by providing er minimal sets of of er of obstructions </S2>
<S3> sorry th- the point is not for me to present what you did i know what you did but you you you have those GFS i don't know if it is very clear what does it means <S2> [mhm] </S2> [but] that means really what that means that you have F you can have variable [you you can (xx) variable you can (permute) variable] </S3>
<S2> [mhm you can (xx) you can (commute)] </S2>
<S3> and then you produce new function and if you produce a new function you say it is (model) </S3>
<S2> yes it's </S2>
<S3> and then you have because of the (xx) </S3>
<S2> mhm , (xx) in terms of (xx) </S2>
<S3> and so your question (xx) is just the initial segment </S3>
<S2> yes exactly it's these things </S2>
<S3> that's a very beautiful result which goes back to to what was the name er <NAME> <NAME> </S3>
<S2> <NAME> <NAME> <NAME> and <NAME> (i've been saying @<NAME> instead of <NAME> @) </S2>
<S3> okay in few sentences what next <S2> mhm </S2> few sentences what next </S3>
<S2> well i i erm i can turn off <SWITCHES OFF THE OVERHEAD PROJECTOR> <S3> just right yes </S3> thank you , well at the moment i i'm working on , well not working i'm starting to work on on two problems , well the first appears in C-3 and the problem can be stated so this appears is motivated by C-3 and the problem can be stated as follows so , what are the automorphisms , in the lattice for the lattice on the lattice <SS> @@ </SS> . of equational classes next erm the next mainly yes i i actually have been working on mhm well it concerns CP-1 in this paper there was posed a problem so we have seen that erm i- in this paper it was shown that er this quasi-ordered set of equivalent classes erm well first of all it can be subdivided into levels and this is due to the fact that each principle initial segment is finite and moreover using a result of <NAME> we were capable of showing that each of these levels is finite so the question is erm i'm going to denote the levels of this partially ordered set by indexed by by er er positive integer or a non-negative integer so the question is how to compute , er the function which takes each erm each non-negative integer to the size of the corresponding level . well er maybe few words on on er okay er maybe yes and the the audience well okay so just to finish still related with my doctoral thesis , the the urgent question is to really erm er disc- er obtain er a deductive , deductive system for functional equations , that is to say erm is to describe the closed sets of functional equations in the galois connections between functions and (equations) </S2>
<S3> i see <S2> and mhm </S2> okay , thank you thank you <STANDS UP> erm okay <WHISPERING> sit down </WHISPERING> </S3>
<S1> <WHISPERING> (xx) usually you stand up </WHISPERING> </S1>
<S3> so good luck so <P:06> so , the candidate has given an overview of his work he has indicated the advances made er presenting the seven paper onto two themes that he has fully illustrated er he has presented i think concrete examples which are the basic of more general result but also roots of of it erm the , he answered my question and seems to me that he's mastering his subject indicated further development and also problem that everybody can see for all those reasons i will recommend the thesis to be accepted </S3>
<S2> thank you very much for er for the for those remarks on my doctoral my doctoral work , so <COUGH> , so if er anyone here has any comments to make on my dissertation <P:11> he or she is requested to ask the <FOREIGN> kustos </FOREIGN> for the floor </S2>
<P:08>
<S1> i declare this discussion closed </S1>
