Kolmogorov complexity and non-determinism
Identifieur interne : 008D82 ( Main/Merge ); précédent : 008D81; suivant : 008D83Kolmogorov 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.
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000887
- to stream PascalFrancis, to step Curation: 000165
- to stream PascalFrancis, to step Checkpoint: 000797
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><idno type="wicri:doubleKey">0304-3975:2002:Grigorieff S:kolmogorov:complexity:and</idno><idno type="wicri:Area/Main/Merge">008D82</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><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/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 008D82 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 008D82 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|type= RBID
|clé= Pascal:02-0172068
|texte= Kolmogorov complexity and non-determinism
}}
| This area was generated with Dilib version V0.6.33. |  |