InforLorV4, PascalFrancis, Corpus, bibRecord, 000608

Linear-time computation of local periods

Identifieur interne : 000608 ( PascalFrancis/Corpus ); précédent : 000607; suivant : 000609

Linear-time computation of local periods

Auteurs : Jean-Pierre Duval ; Roman Kolpakov ; Gregory Kucherov ; Thierry Lecroq ; Arnaud Lefebvre

Source :

Theoretical computer science [ 0304-3975 ] ; 2004.

RBID : Pascal:04-0563887

Descripteurs français

Pascal (Inist)
- Temps linéaire, Temps calcul, Période, Calcul automatique, Mot, Factorisation, Complexité algorithme, Appariement chaîne, Informatique théorique, Algorithme linéaire, Algorithme temps linéaire, Période locale.

English descriptors

KwdEn :
- Algorithm complexity, Computation time, Computer theory, Computing, Factorization, Linear time, Local period, Period, String matching, Word.

Abstract

We present a linear-time algorithm for computing all local periods of a given word. This subsumes (but is substantially more powerful than) the computation of the (global) period of the word and on the other hand, the computation of a critical factorization, implied by the Critical Factorization Theorem.

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 326`
A06				`@2 1-3`
A08	`01`	`1`	`ENG`	`@1 Linear-time computation of local periods`
A11	`01`	`1`		`@1 DUVAL (Jean-Pierre)`
A11	`02`	`1`		`@1 KOLPAKOV (Roman)`
A11	`03`	`1`		`@1 KUCHEROV (Gregory)`
A11	`04`	`1`		`@1 LECROQ (Thierry)`
A11	`05`	`1`		`@1 LEFEBVRE (Arnaud)`
A14	`01`			`@1 LIFAR, Faculty des Sciences et Techniques, Université de Rouen @2 76821 Mont-Saint-Aignan @3 FRA @Z 1 aut.`
A14	`02`			`@1 Complexity Theory and Algorithmics Group, Department of Computer Science, The University of Liverpool, Chadwick Building, Peach Street @2 Liverpool L69 7ZF @3 GBR @Z 2 aut.`
A14	`03`			`@1 INRIA/LORIA, 615 rue du Jardin Botanique, B.P 101 @2 54602 Villers-lès-Nancy @3 FRA @Z 3 aut.`
A14	`04`			`@1 ABISS, Faculté des Sciences et Techniques, University de Rouen @2 76821 Mont-Saint-Aignan @3 FRA @Z 4 aut.`
A14	`05`			`@1 UMR 6037/ABISS, Faculté des Sciences et Techniques, Université de Rouen @2 76821 Mont-Saint-Aignan @3 FRA @Z 5 aut.`
A20				`@1 229-240`
A21				`@1 2004`
A23	`01`			`@0 ENG`
A43	`01`			`@1 INIST @2 17243 @5 354000120453580120`
A44				`@0 0000 @1 © 2004 INIST-CNRS. All rights reserved.`
A45				`@0 31 ref.`
A47	`01`	`1`		`@0 04-0563887`
A60				`@1 P`
A61				`@0 A`
A64	`01`	`1`		`@0 Theoretical computer science`
A66	`01`			`@0 NLD`
C01	`01`		`ENG`	`@0 We present a linear-time algorithm for computing all local periods of a given word. This subsumes (but is substantially more powerful than) the computation of the (global) period of the word and on the other hand, the computation of a critical factorization, implied by the Critical Factorization Theorem.`
C02	`01`	`X`		`@0 001D02A05`
C02	`02`	`X`		`@0 001D02B07B`
C03	`01`	`X`	`FRE`	`@0 Temps linéaire @5 17`
C03	`01`	`X`	`ENG`	`@0 Linear time @5 17`
C03	`01`	`X`	`SPA`	`@0 Tiempo lineal @5 17`
C03	`02`	`X`	`FRE`	`@0 Temps calcul @5 18`
C03	`02`	`X`	`ENG`	`@0 Computation time @5 18`
C03	`02`	`X`	`SPA`	`@0 Tiempo computación @5 18`
C03	`03`	`X`	`FRE`	`@0 Période @5 19`
C03	`03`	`X`	`ENG`	`@0 Period @5 19`
C03	`03`	`X`	`SPA`	`@0 Período @5 19`
C03	`04`	`X`	`FRE`	`@0 Calcul automatique @5 20`
C03	`04`	`X`	`ENG`	`@0 Computing @5 20`
C03	`04`	`X`	`SPA`	`@0 Cálculo automático @5 20`
C03	`05`	`X`	`FRE`	`@0 Mot @5 21`
C03	`05`	`X`	`ENG`	`@0 Word @5 21`
C03	`05`	`X`	`SPA`	`@0 Palabra @5 21`
C03	`06`	`X`	`FRE`	`@0 Factorisation @5 22`
C03	`06`	`X`	`ENG`	`@0 Factorization @5 22`
C03	`06`	`X`	`SPA`	`@0 Factorización @5 22`
C03	`07`	`X`	`FRE`	`@0 Complexité algorithme @5 23`
C03	`07`	`X`	`ENG`	`@0 Algorithm complexity @5 23`
C03	`07`	`X`	`SPA`	`@0 Complejidad algoritmo @5 23`
C03	`08`	`3`	`FRE`	`@0 Appariement chaîne @5 24`
C03	`08`	`3`	`ENG`	`@0 String matching @5 24`
C03	`09`	`X`	`FRE`	`@0 Informatique théorique @5 27`
C03	`09`	`X`	`ENG`	`@0 Computer theory @5 27`
C03	`09`	`X`	`SPA`	`@0 Informática teórica @5 27`
C03	`10`	`X`	`FRE`	`@0 Algorithme linéaire @4 INC @5 70`
C03	`11`	`X`	`FRE`	`@0 Algorithme temps linéaire @4 INC @5 71`
C03	`12`	`X`	`FRE`	`@0 Période locale @4 CD @5 96`
C03	`12`	`X`	`ENG`	`@0 Local period @4 CD @5 96`
N21				`@1 320`
N44	`01`			`@1 OTO`
N82				`@1 OTO`

Format Inist (serveur)

NO :	PASCAL 04-0563887 INIST
ET :	Linear-time computation of local periods
AU :	DUVAL (Jean-Pierre); KOLPAKOV (Roman); KUCHEROV (Gregory); LECROQ (Thierry); LEFEBVRE (Arnaud)
AF :	LIFAR, Faculty des Sciences et Techniques, Université de Rouen/76821 Mont-Saint-Aignan/France (1 aut.); Complexity Theory and Algorithmics Group, Department of Computer Science, The University of Liverpool, Chadwick Building, Peach Street/Liverpool L69 7ZF/Royaume-Uni (2 aut.); INRIA/LORIA, 615 rue du Jardin Botanique, B.P 101/54602 Villers-lès-Nancy/France (3 aut.); ABISS, Faculté des Sciences et Techniques, University de Rouen/76821 Mont-Saint-Aignan/France (4 aut.); UMR 6037/ABISS, Faculté des Sciences et Techniques, Université de Rouen/76821 Mont-Saint-Aignan/France (5 aut.)
DT :	Publication en série; Niveau analytique
SO :	Theoretical computer science; ISSN 0304-3975; Coden TCSCDI; Pays-Bas; Da. 2004; Vol. 326; No. 1-3; Pp. 229-240; Bibl. 31 ref.
LA :	Anglais
EA :	We present a linear-time algorithm for computing all local periods of a given word. This subsumes (but is substantially more powerful than) the computation of the (global) period of the word and on the other hand, the computation of a critical factorization, implied by the Critical Factorization Theorem.
CC :	001D02A05; 001D02B07B
FD :	Temps linéaire; Temps calcul; Période; Calcul automatique; Mot; Factorisation; Complexité algorithme; Appariement chaîne; Informatique théorique; Algorithme linéaire; Algorithme temps linéaire; Période locale
ED :	Linear time; Computation time; Period; Computing; Word; Factorization; Algorithm complexity; String matching; Computer theory; Local period
SD :	Tiempo lineal; Tiempo computación; Período; Cálculo automático; Palabra; Factorización; Complejidad algoritmo; Informática teórica
LO :	INIST-17243.354000120453580120
ID :	04-0563887

Links to Exploration step

Pascal:04-0563887

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Linear-time computation of local periods</title>
<author><name sortKey="Duval, Jean Pierre" sort="Duval, Jean Pierre" uniqKey="Duval J" first="Jean-Pierre" last="Duval">Jean-Pierre Duval</name>
<affiliation><inist:fA14 i1="01"><s1>LIFAR, Faculty des Sciences et Techniques, Université de Rouen</s1>
<s2>76821 Mont-Saint-Aignan</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Kolpakov, Roman" sort="Kolpakov, Roman" uniqKey="Kolpakov R" first="Roman" last="Kolpakov">Roman Kolpakov</name>
<affiliation><inist:fA14 i1="02"><s1>Complexity Theory and Algorithmics Group, Department of Computer Science, The University of Liverpool, Chadwick Building, Peach Street</s1>
<s2>Liverpool L69 7ZF</s2>
<s3>GBR</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
<affiliation><inist:fA14 i1="03"><s1>INRIA/LORIA, 615 rue du Jardin Botanique, B.P 101</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Lecroq, Thierry" sort="Lecroq, Thierry" uniqKey="Lecroq T" first="Thierry" last="Lecroq">Thierry Lecroq</name>
<affiliation><inist:fA14 i1="04"><s1>ABISS, Faculté des Sciences et Techniques, University de Rouen</s1>
<s2>76821 Mont-Saint-Aignan</s2>
<s3>FRA</s3>
<sZ>4 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Lefebvre, Arnaud" sort="Lefebvre, Arnaud" uniqKey="Lefebvre A" first="Arnaud" last="Lefebvre">Arnaud Lefebvre</name>
<affiliation><inist:fA14 i1="05"><s1>UMR 6037/ABISS, Faculté des Sciences et Techniques, Université de Rouen</s1>
<s2>76821 Mont-Saint-Aignan</s2>
<s3>FRA</s3>
<sZ>5 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">04-0563887</idno>
<date when="2004">2004</date>
<idno type="stanalyst">PASCAL 04-0563887 INIST</idno>
<idno type="RBID">Pascal:04-0563887</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000608</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Linear-time computation of local periods</title>
<author><name sortKey="Duval, Jean Pierre" sort="Duval, Jean Pierre" uniqKey="Duval J" first="Jean-Pierre" last="Duval">Jean-Pierre Duval</name>
<affiliation><inist:fA14 i1="01"><s1>LIFAR, Faculty des Sciences et Techniques, Université de Rouen</s1>
<s2>76821 Mont-Saint-Aignan</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Kolpakov, Roman" sort="Kolpakov, Roman" uniqKey="Kolpakov R" first="Roman" last="Kolpakov">Roman Kolpakov</name>
<affiliation><inist:fA14 i1="02"><s1>Complexity Theory and Algorithmics Group, Department of Computer Science, The University of Liverpool, Chadwick Building, Peach Street</s1>
<s2>Liverpool L69 7ZF</s2>
<s3>GBR</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
<affiliation><inist:fA14 i1="03"><s1>INRIA/LORIA, 615 rue du Jardin Botanique, B.P 101</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Lecroq, Thierry" sort="Lecroq, Thierry" uniqKey="Lecroq T" first="Thierry" last="Lecroq">Thierry Lecroq</name>
<affiliation><inist:fA14 i1="04"><s1>ABISS, Faculté des Sciences et Techniques, University de Rouen</s1>
<s2>76821 Mont-Saint-Aignan</s2>
<s3>FRA</s3>
<sZ>4 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Lefebvre, Arnaud" sort="Lefebvre, Arnaud" uniqKey="Lefebvre A" first="Arnaud" last="Lefebvre">Arnaud Lefebvre</name>
<affiliation><inist:fA14 i1="05"><s1>UMR 6037/ABISS, Faculté des Sciences et Techniques, Université de Rouen</s1>
<s2>76821 Mont-Saint-Aignan</s2>
<s3>FRA</s3>
<sZ>5 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="2004">2004</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>Algorithm complexity</term>
<term>Computation time</term>
<term>Computer theory</term>
<term>Computing</term>
<term>Factorization</term>
<term>Linear time</term>
<term>Local period</term>
<term>Period</term>
<term>String matching</term>
<term>Word</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Temps linéaire</term>
<term>Temps calcul</term>
<term>Période</term>
<term>Calcul automatique</term>
<term>Mot</term>
<term>Factorisation</term>
<term>Complexité algorithme</term>
<term>Appariement chaîne</term>
<term>Informatique théorique</term>
<term>Algorithme linéaire</term>
<term>Algorithme temps linéaire</term>
<term>Période locale</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">We present a linear-time algorithm for computing all local periods of a given word. This subsumes (but is substantially more powerful than) the computation of the (global) period of the word and on the other hand, the computation of a critical factorization, implied by the Critical Factorization Theorem.</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>326</s2>
</fA05>
<fA06><s2>1-3</s2>
</fA06>
<fA08 i1="01" i2="1" l="ENG"><s1>Linear-time computation of local periods</s1>
</fA08>
<fA11 i1="01" i2="1"><s1>DUVAL (Jean-Pierre)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>KOLPAKOV (Roman)</s1>
</fA11>
<fA11 i1="03" i2="1"><s1>KUCHEROV (Gregory)</s1>
</fA11>
<fA11 i1="04" i2="1"><s1>LECROQ (Thierry)</s1>
</fA11>
<fA11 i1="05" i2="1"><s1>LEFEBVRE (Arnaud)</s1>
</fA11>
<fA14 i1="01"><s1>LIFAR, Faculty des Sciences et Techniques, Université de Rouen</s1>
<s2>76821 Mont-Saint-Aignan</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</fA14>
<fA14 i1="02"><s1>Complexity Theory and Algorithmics Group, Department of Computer Science, The University of Liverpool, Chadwick Building, Peach Street</s1>
<s2>Liverpool L69 7ZF</s2>
<s3>GBR</s3>
<sZ>2 aut.</sZ>
</fA14>
<fA14 i1="03"><s1>INRIA/LORIA, 615 rue du Jardin Botanique, B.P 101</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>3 aut.</sZ>
</fA14>
<fA14 i1="04"><s1>ABISS, Faculté des Sciences et Techniques, University de Rouen</s1>
<s2>76821 Mont-Saint-Aignan</s2>
<s3>FRA</s3>
<sZ>4 aut.</sZ>
</fA14>
<fA14 i1="05"><s1>UMR 6037/ABISS, Faculté des Sciences et Techniques, Université de Rouen</s1>
<s2>76821 Mont-Saint-Aignan</s2>
<s3>FRA</s3>
<sZ>5 aut.</sZ>
</fA14>
<fA20><s1>229-240</s1>
</fA20>
<fA21><s1>2004</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA43 i1="01"><s1>INIST</s1>
<s2>17243</s2>
<s5>354000120453580120</s5>
</fA43>
<fA44><s0>0000</s0>
<s1>© 2004 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45><s0>31 ref.</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>04-0563887</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 present a linear-time algorithm for computing all local periods of a given word. This subsumes (but is substantially more powerful than) the computation of the (global) period of the word and on the other hand, the computation of a critical factorization, implied by the Critical Factorization Theorem.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001D02A05</s0>
</fC02>
<fC02 i1="02" i2="X"><s0>001D02B07B</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE"><s0>Temps linéaire</s0>
<s5>17</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG"><s0>Linear time</s0>
<s5>17</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA"><s0>Tiempo lineal</s0>
<s5>17</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE"><s0>Temps calcul</s0>
<s5>18</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG"><s0>Computation time</s0>
<s5>18</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA"><s0>Tiempo computación</s0>
<s5>18</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE"><s0>Période</s0>
<s5>19</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG"><s0>Period</s0>
<s5>19</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA"><s0>Período</s0>
<s5>19</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE"><s0>Calcul automatique</s0>
<s5>20</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG"><s0>Computing</s0>
<s5>20</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA"><s0>Cálculo automático</s0>
<s5>20</s5>
</fC03>
<fC03 i1="05" i2="X" l="FRE"><s0>Mot</s0>
<s5>21</s5>
</fC03>
<fC03 i1="05" i2="X" l="ENG"><s0>Word</s0>
<s5>21</s5>
</fC03>
<fC03 i1="05" i2="X" l="SPA"><s0>Palabra</s0>
<s5>21</s5>
</fC03>
<fC03 i1="06" i2="X" l="FRE"><s0>Factorisation</s0>
<s5>22</s5>
</fC03>
<fC03 i1="06" i2="X" l="ENG"><s0>Factorization</s0>
<s5>22</s5>
</fC03>
<fC03 i1="06" i2="X" l="SPA"><s0>Factorización</s0>
<s5>22</s5>
</fC03>
<fC03 i1="07" i2="X" l="FRE"><s0>Complexité algorithme</s0>
<s5>23</s5>
</fC03>
<fC03 i1="07" i2="X" l="ENG"><s0>Algorithm complexity</s0>
<s5>23</s5>
</fC03>
<fC03 i1="07" i2="X" l="SPA"><s0>Complejidad algoritmo</s0>
<s5>23</s5>
</fC03>
<fC03 i1="08" i2="3" l="FRE"><s0>Appariement chaîne</s0>
<s5>24</s5>
</fC03>
<fC03 i1="08" i2="3" l="ENG"><s0>String matching</s0>
<s5>24</s5>
</fC03>
<fC03 i1="09" i2="X" l="FRE"><s0>Informatique théorique</s0>
<s5>27</s5>
</fC03>
<fC03 i1="09" i2="X" l="ENG"><s0>Computer theory</s0>
<s5>27</s5>
</fC03>
<fC03 i1="09" i2="X" l="SPA"><s0>Informática teórica</s0>
<s5>27</s5>
</fC03>
<fC03 i1="10" i2="X" l="FRE"><s0>Algorithme linéaire</s0>
<s4>INC</s4>
<s5>70</s5>
</fC03>
<fC03 i1="11" i2="X" l="FRE"><s0>Algorithme temps linéaire</s0>
<s4>INC</s4>
<s5>71</s5>
</fC03>
<fC03 i1="12" i2="X" l="FRE"><s0>Période locale</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="12" i2="X" l="ENG"><s0>Local period</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fN21><s1>320</s1>
</fN21>
<fN44 i1="01"><s1>OTO</s1>
</fN44>
<fN82><s1>OTO</s1>
</fN82>
</pA>
</standard>
<server><NO>PASCAL 04-0563887 INIST</NO>
<ET>Linear-time computation of local periods</ET>
<AU>DUVAL (Jean-Pierre); KOLPAKOV (Roman); KUCHEROV (Gregory); LECROQ (Thierry); LEFEBVRE (Arnaud)</AU>
<AF>LIFAR, Faculty des Sciences et Techniques, Université de Rouen/76821 Mont-Saint-Aignan/France (1 aut.); Complexity Theory and Algorithmics Group, Department of Computer Science, The University of Liverpool, Chadwick Building, Peach Street/Liverpool L69 7ZF/Royaume-Uni (2 aut.); INRIA/LORIA, 615 rue du Jardin Botanique, B.P 101/54602 Villers-lès-Nancy/France (3 aut.); ABISS, Faculté des Sciences et Techniques, University de Rouen/76821 Mont-Saint-Aignan/France (4 aut.); UMR 6037/ABISS, Faculté des Sciences et Techniques, Université de Rouen/76821 Mont-Saint-Aignan/France (5 aut.)</AF>
<DT>Publication en série; Niveau analytique</DT>
<SO>Theoretical computer science; ISSN 0304-3975; Coden TCSCDI; Pays-Bas; Da. 2004; Vol. 326; No. 1-3; Pp. 229-240; Bibl. 31 ref.</SO>
<LA>Anglais</LA>
<EA>We present a linear-time algorithm for computing all local periods of a given word. This subsumes (but is substantially more powerful than) the computation of the (global) period of the word and on the other hand, the computation of a critical factorization, implied by the Critical Factorization Theorem.</EA>
<CC>001D02A05; 001D02B07B</CC>
<FD>Temps linéaire; Temps calcul; Période; Calcul automatique; Mot; Factorisation; Complexité algorithme; Appariement chaîne; Informatique théorique; Algorithme linéaire; Algorithme temps linéaire; Période locale</FD>
<ED>Linear time; Computation time; Period; Computing; Word; Factorization; Algorithm complexity; String matching; Computer theory; Local period</ED>
<SD>Tiempo lineal; Tiempo computación; Período; Cálculo automático; Palabra; Factorización; Complejidad algoritmo; Informática teórica</SD>
<LO>INIST-17243.354000120453580120</LO>
<ID>04-0563887</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 000608 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000608 | 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:04-0563887
   |texte=   Linear-time computation of local periods
}}

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

Linear-time computation of local periods

Linear-time computation of local periods

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