InforLorV4, PascalFrancis, Corpus, bibRecord, 000887

Kolmogorov complexity and non-determinism

Identifieur interne : 000887 ( PascalFrancis/Corpus ); précédent : 000886; suivant : 000888

Kolmogorov complexity and non-determinism

Auteurs : Serge Grigorieff ; Jean-Yves Marion

Source :

Theoretical computer science [ 0304-3975 ] ; 2002.

RBID : Pascal:02-0172068

Descripteurs français

Pascal (Inist)
- Théorie information, Complexité, Non déterminisme, Donnée binaire, Suite binaire, Complexité Kolmogorov, Mode préfixe.

English descriptors

KwdEn :
- Binary data, Binary string, Complexity, Information theory, Kolmogorov complexity, Non determinism, Prefix mode.

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.

Notice en format standard (ISO 2709)

Pour connaître la documentation sur le format Inist Standard.

A01	`01`	`1`		`@0 0304-3975`
A02	`01`			`@0 TCSCDI`
A03		`1`		`@0 Theor. comput. sci.`
A05				`@2 271`
A06				`@2 1-2`
A08	`01`	`1`	`ENG`	`@1 Kolmogorov complexity and non-determinism`
A09	`01`	`1`	`ENG`	`@1 Kolmogorov complexity`
A11	`01`	`1`		`@1 GRIGORIEFF (Serge)`
A11	`02`	`1`		`@1 MARION (Jean-Yves)`
A12	`01`	`1`		`@1 DURAND (Bruno) @9 ed.`
A14	`01`			`@1 Université Paris 7, UFR d'lnformatique, 2 Place Jussieu @2 75251 Paris @3 FRA @Z 1 aut.`
A14	`02`			`@1 Laboratoire LLAIC, Université Clermont-Ferrand 1 @3 FRA @Z 1 aut.`
A14	`03`			`@1 LORIA, Université Nancy 2, Calligramme Project, B.P. 239 @2 54506 Vandœuvre-lès-Nancy @3 FRA @Z 2 aut.`
A15	`01`			`@1 LIM - CMI, Université de Provence, 39 rue Jolliot-Curie @2 13453 Marseille @3 FRA @Z 1 aut.`
A20				`@1 151-180`
A21				`@1 2002`
A23	`01`			`@0 ENG`
A43	`01`			`@1 INIST @2 17243 @5 354000103453390120`
A44				`@0 0000 @1 © 2002 INIST-CNRS. All rights reserved.`
A45				`@0 11 ref.`
A47	`01`	`1`		`@0 02-0172068`
A60				`@1 P`
A61				`@0 A`
A64	`01`	`1`		`@0 Theoretical computer science`
A66	`01`			`@0 NLD`
C01	`01`		`ENG`	@0 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.
C02	`01`	`X`		`@0 001D02A05`
C03	`01`	`X`	`FRE`	`@0 Théorie information @5 01`
C03	`01`	`X`	`ENG`	`@0 Information theory @5 01`
C03	`01`	`X`	`SPA`	`@0 Teoría información @5 01`
C03	`02`	`X`	`FRE`	`@0 Complexité @5 02`
C03	`02`	`X`	`ENG`	`@0 Complexity @5 02`
C03	`02`	`X`	`SPA`	`@0 Complejidad @5 02`
C03	`03`	`X`	`FRE`	`@0 Non déterminisme @5 03`
C03	`03`	`X`	`ENG`	`@0 Non determinism @5 03`
C03	`03`	`X`	`SPA`	`@0 No determinismo @5 03`
C03	`04`	`X`	`FRE`	`@0 Donnée binaire @5 04`
C03	`04`	`X`	`ENG`	`@0 Binary data @5 04`
C03	`04`	`X`	`SPA`	`@0 Dato binario @5 04`
C03	`05`	`X`	`FRE`	`@0 Suite binaire @4 CD @5 96`
C03	`05`	`X`	`ENG`	`@0 Binary string @4 CD @5 96`
C03	`06`	`X`	`FRE`	`@0 Complexité Kolmogorov @4 CD @5 97`
C03	`06`	`X`	`ENG`	`@0 Kolmogorov complexity @4 CD @5 97`
C03	`07`	`X`	`FRE`	`@0 Mode préfixe @4 CD @5 98`
C03	`07`	`X`	`ENG`	`@0 Prefix mode @4 CD @5 98`
N21				`@1 098`

Format Inist (serveur)

NO :	PASCAL 02-0172068 INIST
ET :	Kolmogorov complexity and non-determinism
AU :	GRIGORIEFF (Serge); MARION (Jean-Yves); DURAND (Bruno)
AF :	Université Paris 7, UFR d'lnformatique, 2 Place Jussieu/75251 Paris/France (1 aut.); Laboratoire LLAIC, Université Clermont-Ferrand 1/France (1 aut.); LORIA, Université Nancy 2, Calligramme Project, B.P. 239/54506 Vandœuvre-lès-Nancy/France (2 aut.); LIM - CMI, Université de Provence, 39 rue Jolliot-Curie/13453 Marseille/France (1 aut.)
DT :	Publication en série; Niveau analytique
SO :	Theoretical computer science; ISSN 0304-3975; Coden TCSCDI; Pays-Bas; Da. 2002; Vol. 271; No. 1-2; Pp. 151-180; Bibl. 11 ref.
LA :	Anglais
EA :	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.
CC :	001D02A05
FD :	Théorie information; Complexité; Non déterminisme; Donnée binaire; Suite binaire; Complexité Kolmogorov; Mode préfixe
ED :	Information theory; Complexity; Non determinism; Binary data; Binary string; Kolmogorov complexity; Prefix mode
SD :	Teoría información; Complejidad; No determinismo; Dato binario
LO :	INIST-17243.354000103453390120
ID :	02-0172068

Links to Exploration step

Pascal:02-0172068

Le 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><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>
</affiliation>
<affiliation><inist:fA14 i1="02"><s1>Laboratoire LLAIC, Université Clermont-Ferrand 1</s1>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</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><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>
</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>
</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><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>
</affiliation>
<affiliation><inist:fA14 i1="02"><s1>Laboratoire LLAIC, Université Clermont-Ferrand 1</s1>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</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><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>
</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>
<server><NO>PASCAL 02-0172068 INIST</NO>
<ET>Kolmogorov complexity and non-determinism</ET>
<AU>GRIGORIEFF (Serge); MARION (Jean-Yves); DURAND (Bruno)</AU>
<AF>Université Paris 7, UFR d'lnformatique, 2 Place Jussieu/75251 Paris/France (1 aut.); Laboratoire LLAIC, Université Clermont-Ferrand 1/France (1 aut.); LORIA, Université Nancy 2, Calligramme Project, B.P. 239/54506 Vandœuvre-lès-Nancy/France (2 aut.); LIM - CMI, Université de Provence, 39 rue Jolliot-Curie/13453 Marseille/France (1 aut.)</AF>
<DT>Publication en série; Niveau analytique</DT>
<SO>Theoretical computer science; ISSN 0304-3975; Coden TCSCDI; Pays-Bas; Da. 2002; Vol. 271; No. 1-2; Pp. 151-180; Bibl. 11 ref.</SO>
<LA>Anglais</LA>
<EA>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.</EA>
<CC>001D02A05</CC>
<FD>Théorie information; Complexité; Non déterminisme; Donnée binaire; Suite binaire; Complexité Kolmogorov; Mode préfixe</FD>
<ED>Information theory; Complexity; Non determinism; Binary data; Binary string; Kolmogorov complexity; Prefix mode</ED>
<SD>Teoría información; Complejidad; No determinismo; Dato binario</SD>
<LO>INIST-17243.354000103453390120</LO>
<ID>02-0172068</ID>
</server>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000887 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000887 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    PascalFrancis
   |étape=   Corpus
   |type=    RBID
   |clé=     Pascal:02-0172068
   |texte=   Kolmogorov complexity and non-determinism
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

Kolmogorov complexity and non-determinism

Kolmogorov complexity and non-determinism

Source :

Descripteurs français

English descriptors

Abstract

Notice en format standard (ISO 2709)

Format Inist (serveur)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri