DIMACS Series in Discrete Mathematics and Theoretical Comput

Abstract. The notion of relative closure (X, Y)0 of a semi-Pfaffian couple (X, Y) was introduced by Gabrielov to give a description of the o-minimal structure generated by Pfaffian functions. In this paper, an effective bound is given for the number of con

DIMACSSeriesinDiscreteMathematics

andTheoreticalComputerScience

OntheNumberofConnectedComponentsoftheRelative

ClosureofaSemi-Pfa anFamily

AndreiGabrielovandThierryZell

Abstract.Thenotionofrelativeclosure(X,Y)0ofasemi-Pfa ancouple

(X,Y)wasintroducedbyGabrielovtogiveadescriptionoftheo-minimal

structuregeneratedbyPfa anfunctions.Inthispaper,ane ectivebound

isgivenforthenumberofconnectedcomponentsof(X,Y)0intermsofthe

Pfa ancomplexityofXandY.

Introduction

Pfa anfunctionsarerealanalyticfunctionsthataresolutionstocertaintrian-gularsystemsofpolynomialpartialdi erentialequations(seeDe nition1).TheywereintroducedbyKhovanski [12],whoshowedthatthesetranscendentalfunc-tionsexhibit,intherealdomain,global nitenesspropertiessimilartotheproper-tiesofpolynomials.Itfollowsinturnthatthegeometricalandtopologicalcharac-teristicsofsetsde nedusingPfa anfunctionsarealsowellcontrolled.E ectiveupperboundsforthosegeometricpropertiescanbefoundin[3,5,7,8,18,22].

O-minimalityisanaturalframeworkforthestudyofPfa anfunctions.(ThereadercanrefertovandenDries[2]forde nitions.)Wilkieprovedin[21]thatthestructuregeneratedbyPfa anfunctionsiso-minimal(seealso[9,19]forgeneralizationsofthisresult.)

In[6],Gabrielovintroducedthenotionofrelativeclosureofasemi-Pfa ancouple,asanalternativetoWilkie’sconstruction.Inthisway,heobtainedano-minimalstructureinwhichde nablesets(calledlimitsets)haveasimplepresen-tation.Asaresult,thisstructuresupportsanotionofcomplexitywhichnaturallyextendstheusualPfa ancomplexity,andallowsonetoestimatethecomplexityofBooleanoperationsinthatstructure.

Inthispaper,weusethisnotionofcomplexitytogiveanexplicitboundonthenumberofconnectedcomponentsofalimitset.Inthe rstpart,werecalltheusualde nitionsrelatedtoPfa anfunctions,thenwecovertheessentialmaterialwewillusefrom[6].Inthesecondpart,wegiveexplicitboundsforthesmoothcase(Theorem15)andforthegeneralcase(Theorem17).Section3isdevotedtotwoapplicationstothefewnomialcase:Theorem19andTheorem20.

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库DIMACS Series in Discrete Mathematics and Theoretical Comput在线全文阅读。