Kolmogorov complexity and non-determinism
Identifieur interne : 000797 ( PascalFrancis/Checkpoint ); précédent : 000796; suivant : 000798Kolmogorov complexity and non-determinism
Auteurs : Serge Grigorieff [France] ; Jean-Yves Marion [France]Source :
- Theoretical computer science [ 0304-3975 ] ; 2002.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
We are concerned with Kolmogorov complexity of strings produced by non-deterministic algorithms. For this, we consider five classes of non-deterministic description modes: (i) non-bounded description modes in which the number of outputs depends on programs, (ii) distributed description modes in which the number of outputs depends on the size of the outputs, (iii) spread description modes in which the number of outputs depends on both programs and the size of the outputs, (iv) description modes for which each string has a unique minimal description, and lastly (v) description modes for which the set of minimal length descriptions is a prefix set.
Affiliations:
Links toward previous steps (curation, corpus...)
Links to Exploration step
Pascal:02-0172068Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Kolmogorov complexity and non-determinism</title><author><name sortKey="Grigorieff, Serge" sort="Grigorieff, Serge" uniqKey="Grigorieff S" first="Serge" last="Grigorieff">Serge Grigorieff</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Université Paris 7, UFR d'lnformatique, 2 Place Jussieu</s1><s2>75251 Paris</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">Paris</settlement></placeName></affiliation><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Laboratoire LLAIC, Université Clermont-Ferrand 1</s1><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><wicri:noRegion>Université Clermont-Ferrand 1</wicri:noRegion><wicri:noRegion>Laboratoire LLAIC, Université Clermont-Ferrand 1</wicri:noRegion></affiliation></author><author><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name><affiliation wicri:level="4"><inist:fA14 i1="03"><s1>LORIA, Université Nancy 2, Calligramme Project, B.P. 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>2 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Vandœuvre-lès-Nancy</settlement></placeName><orgName type="university">Université Nancy 2</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">02-0172068</idno><date when="2002">2002</date><idno type="stanalyst">PASCAL 02-0172068 INIST</idno><idno type="RBID">Pascal:02-0172068</idno><idno type="wicri:Area/PascalFrancis/Corpus">000887</idno><idno type="wicri:Area/PascalFrancis/Curation">000165</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000797</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000797</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Kolmogorov complexity and non-determinism</title><author><name sortKey="Grigorieff, Serge" sort="Grigorieff, Serge" uniqKey="Grigorieff S" first="Serge" last="Grigorieff">Serge Grigorieff</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Université Paris 7, UFR d'lnformatique, 2 Place Jussieu</s1><s2>75251 Paris</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">Paris</settlement></placeName></affiliation><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Laboratoire LLAIC, Université Clermont-Ferrand 1</s1><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><wicri:noRegion>Université Clermont-Ferrand 1</wicri:noRegion><wicri:noRegion>Laboratoire LLAIC, Université Clermont-Ferrand 1</wicri:noRegion></affiliation></author><author><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name><affiliation wicri:level="4"><inist:fA14 i1="03"><s1>LORIA, Université Nancy 2, Calligramme Project, B.P. 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>2 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Vandœuvre-lès-Nancy</settlement></placeName><orgName type="university">Université Nancy 2</orgName></affiliation></author></analytic><series><title level="j" type="main">Theoretical computer science</title><title level="j" type="abbreviated">Theor. comput. sci.</title><idno type="ISSN">0304-3975</idno><imprint><date when="2002">2002</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Theoretical computer science</title><title level="j" type="abbreviated">Theor. comput. sci.</title><idno type="ISSN">0304-3975</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Binary data</term><term>Binary string</term><term>Complexity</term><term>Information theory</term><term>Kolmogorov complexity</term><term>Non determinism</term><term>Prefix mode</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Théorie information</term><term>Complexité</term><term>Non déterminisme</term><term>Donnée binaire</term><term>Suite binaire</term><term>Complexité Kolmogorov</term><term>Mode préfixe</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We are concerned with Kolmogorov complexity of strings produced by non-deterministic algorithms. For this, we consider five classes of non-deterministic description modes: (i) non-bounded description modes in which the number of outputs depends on programs, (ii) distributed description modes in which the number of outputs depends on the size of the outputs, (iii) spread description modes in which the number of outputs depends on both programs and the size of the outputs, (iv) description modes for which each string has a unique minimal description, and lastly (v) description modes for which the set of minimal length descriptions is a prefix set.</div></front></TEI><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0304-3975</s0></fA01><fA02 i1="01"><s0>TCSCDI</s0></fA02><fA03 i2="1"><s0>Theor. comput. sci.</s0></fA03><fA05><s2>271</s2></fA05><fA06><s2>1-2</s2></fA06><fA08 i1="01" i2="1" l="ENG"><s1>Kolmogorov complexity and non-determinism</s1></fA08><fA09 i1="01" i2="1" l="ENG"><s1>Kolmogorov complexity</s1></fA09><fA11 i1="01" i2="1"><s1>GRIGORIEFF (Serge)</s1></fA11><fA11 i1="02" i2="1"><s1>MARION (Jean-Yves)</s1></fA11><fA12 i1="01" i2="1"><s1>DURAND (Bruno)</s1><s9>ed.</s9></fA12><fA14 i1="01"><s1>Université Paris 7, UFR d'lnformatique, 2 Place Jussieu</s1><s2>75251 Paris</s2><s3>FRA</s3><sZ>1 aut.</sZ></fA14><fA14 i1="02"><s1>Laboratoire LLAIC, Université Clermont-Ferrand 1</s1><s3>FRA</s3><sZ>1 aut.</sZ></fA14><fA14 i1="03"><s1>LORIA, Université Nancy 2, Calligramme Project, B.P. 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>2 aut.</sZ></fA14><fA15 i1="01"><s1>LIM - CMI, Université de Provence, 39 rue Jolliot-Curie</s1><s2>13453 Marseille</s2><s3>FRA</s3><sZ>1 aut.</sZ></fA15><fA20><s1>151-180</s1></fA20><fA21><s1>2002</s1></fA21><fA23 i1="01"><s0>ENG</s0></fA23><fA43 i1="01"><s1>INIST</s1><s2>17243</s2><s5>354000103453390120</s5></fA43><fA44><s0>0000</s0><s1>© 2002 INIST-CNRS. All rights reserved.</s1></fA44><fA45><s0>11 ref.</s0></fA45><fA47 i1="01" i2="1"><s0>02-0172068</s0></fA47><fA60><s1>P</s1></fA60><fA61><s0>A</s0></fA61><fA64 i1="01" i2="1"><s0>Theoretical computer science</s0></fA64><fA66 i1="01"><s0>NLD</s0></fA66><fC01 i1="01" l="ENG"><s0>We are concerned with Kolmogorov complexity of strings produced by non-deterministic algorithms. For this, we consider five classes of non-deterministic description modes: (i) non-bounded description modes in which the number of outputs depends on programs, (ii) distributed description modes in which the number of outputs depends on the size of the outputs, (iii) spread description modes in which the number of outputs depends on both programs and the size of the outputs, (iv) description modes for which each string has a unique minimal description, and lastly (v) description modes for which the set of minimal length descriptions is a prefix set.</s0></fC01><fC02 i1="01" i2="X"><s0>001D02A05</s0></fC02><fC03 i1="01" i2="X" l="FRE"><s0>Théorie information</s0><s5>01</s5></fC03><fC03 i1="01" i2="X" l="ENG"><s0>Information theory</s0><s5>01</s5></fC03><fC03 i1="01" i2="X" l="SPA"><s0>Teoría información</s0><s5>01</s5></fC03><fC03 i1="02" i2="X" l="FRE"><s0>Complexité</s0><s5>02</s5></fC03><fC03 i1="02" i2="X" l="ENG"><s0>Complexity</s0><s5>02</s5></fC03><fC03 i1="02" i2="X" l="SPA"><s0>Complejidad</s0><s5>02</s5></fC03><fC03 i1="03" i2="X" l="FRE"><s0>Non déterminisme</s0><s5>03</s5></fC03><fC03 i1="03" i2="X" l="ENG"><s0>Non determinism</s0><s5>03</s5></fC03><fC03 i1="03" i2="X" l="SPA"><s0>No determinismo</s0><s5>03</s5></fC03><fC03 i1="04" i2="X" l="FRE"><s0>Donnée binaire</s0><s5>04</s5></fC03><fC03 i1="04" i2="X" l="ENG"><s0>Binary data</s0><s5>04</s5></fC03><fC03 i1="04" i2="X" l="SPA"><s0>Dato binario</s0><s5>04</s5></fC03><fC03 i1="05" i2="X" l="FRE"><s0>Suite binaire</s0><s4>CD</s4><s5>96</s5></fC03><fC03 i1="05" i2="X" l="ENG"><s0>Binary string</s0><s4>CD</s4><s5>96</s5></fC03><fC03 i1="06" i2="X" l="FRE"><s0>Complexité Kolmogorov</s0><s4>CD</s4><s5>97</s5></fC03><fC03 i1="06" i2="X" l="ENG"><s0>Kolmogorov complexity</s0><s4>CD</s4><s5>97</s5></fC03><fC03 i1="07" i2="X" l="FRE"><s0>Mode préfixe</s0><s4>CD</s4><s5>98</s5></fC03><fC03 i1="07" i2="X" l="ENG"><s0>Prefix mode</s0><s4>CD</s4><s5>98</s5></fC03><fN21><s1>098</s1></fN21></pA></standard></inist><affiliations><list><country><li>France</li></country><region><li>Grand Est</li><li>Lorraine (région)</li><li>Île-de-France</li></region><settlement><li>Paris</li><li>Vandœuvre-lès-Nancy</li></settlement><orgName><li>Université Nancy 2</li></orgName></list><tree><country name="France"><region name="Île-de-France"><name sortKey="Grigorieff, Serge" sort="Grigorieff, Serge" uniqKey="Grigorieff S" first="Serge" last="Grigorieff">Serge Grigorieff</name></region><name sortKey="Grigorieff, Serge" sort="Grigorieff, Serge" uniqKey="Grigorieff S" first="Serge" last="Grigorieff">Serge Grigorieff</name><name sortKey="Marion, Jean Yves" sort="Marion, Jean Yves" uniqKey="Marion J" first="Jean-Yves" last="Marion">Jean-Yves Marion</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000797 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Checkpoint/biblio.hfd -nk 000797 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Checkpoint
|type= RBID
|clé= Pascal:02-0172068
|texte= Kolmogorov complexity and non-determinism
}}
| This area was generated with Dilib version V0.6.33. |  |