Analysis of the Symbols Table in D.E. Knuth's Model
Identifieur interne : 000984 ( Crin/Corpus ); précédent : 000983; suivant : 000985Analysis of the Symbols Table in D.E. Knuth's Model
Auteurs : P. Feinsilver ; R. SchottSource :
English descriptors
Abstract
In this paper we analyze the average behaviour of the symbol table in the statistical model introduced by J. Françon and D.E. Knuth\, : if the size of the dynamic data structure is k, then the number of possibilities is equal to one for a deletion and 4 for a positive query, but the number of possibilities for the i-th insertion is equal to i. This data structure gives rise to very difficult combinatorial problems and novel ideas are used in the analysis since the classical methods do not apply.
Links to Exploration step
CRIN:feinsilver90bLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="143">Analysis of the Symbols Table in D.E. Knuth's Model</title></titleStmt><publicationStmt><idno type="RBID">CRIN:feinsilver90b</idno><date when="1990" year="1990">1990</date><idno type="wicri:Area/Crin/Corpus">000984</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Analysis of the Symbols Table in D.E. Knuth's Model</title><author><name sortKey="Feinsilver, P" sort="Feinsilver, P" uniqKey="Feinsilver P" first="P." last="Feinsilver">P. Feinsilver</name></author><author><name sortKey="Schott, R" sort="Schott, R" uniqKey="Schott R" first="R." last="Schott">R. Schott</name></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Bessel functions</term><term>Lommel polynoimia</term><term>dynamic algorithm</term><term>symbol table</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="1002">In this paper we analyze the average behaviour of the symbol table in the statistical model introduced by J. Françon and D.E. Knuth\, : if the size of the dynamic data structure is k, then the number of possibilities is equal to one for a deletion and 4 for a positive query, but the number of possibilities for the i-th insertion is equal to i. This data structure gives rise to very difficult combinatorial problems and novel ideas are used in the analysis since the classical methods do not apply.</div></front></TEI><BibTex type="techreport"><ref>feinsilver90b</ref><crinnumber>90-R-156</crinnumber><category>15</category><equipe>EURECA</equipe><author><e>Feinsilver, P.</e><e>Schott, R.</e></author><title>Analysis of the Symbols Table in D.E. Knuth's Model</title><institution>Centre de Recherche en Informatique de Nancy</institution><year>1990</year><type>Rapport interne</type><address>Vandoeuvre-lès-Nancy</address><keywords><e>dynamic algorithm</e><e>symbol table</e><e>Bessel functions</e><e>Lommel polynoimia</e></keywords><abstract>In this paper we analyze the average behaviour of the symbol table in the statistical model introduced by J. Françon and D.E. Knuth\, : if the size of the dynamic data structure is k, then the number of possibilities is equal to one for a deletion and 4 for a positive query, but the number of possibilities for the i-th insertion is equal to i. This data structure gives rise to very difficult combinatorial problems and novel ideas are used in the analysis since the classical methods do not apply.</abstract></BibTex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Crin/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000984 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Crin/Corpus/biblio.hfd -nk 000984 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Crin
|étape= Corpus
|type= RBID
|clé= CRIN:feinsilver90b
|texte= Analysis of the Symbols Table in D.E. Knuth's Model
}}
| This area was generated with Dilib version V0.6.33. |  |