InforLorV4, PascalFrancis, Corpus, bibRecord, 000A89

On maximal repetitions in words

Identifieur interne : 000A89 ( PascalFrancis/Corpus ); précédent : 000A88; suivant : 000A90

On maximal repetitions in words

Auteurs : R. Kolpakov ; G. Kucherov

Source :

Lecture notes in computer science [ 0302-9743 ] ; 1999.

RBID : Pascal:99-0526090

Descripteurs français

Pascal (Inist)
- Répétition, Longueur mot, Temps linéaire, Algorithmique, Maximal repetition in word, Mot Fibonacci, Mot binaire.

English descriptors

KwdEn :
- Algorithmics, Linear time, Repetition, Word length.

Abstract

A (fractional) repetition in a word w is a subword with the period of at most half of the subword length. We study maximal repetitions occurring in w, that is those for which any extended subword of w has a bigger period. The set of such repetitions represents in a compact way all repetitions in w. We first study maximal repetitions in Fibonacci words - we count their exact number, and estimate the sum of their exponents. These quantities turn out to be linearly-bounded in the length of the word. We then prove that the maximal number of maximal repetitions in general words (on arbitrary alphabet) of length n is linearly-bounded in n, and we mention some applications and consequences of this result.

Notice en format standard (ISO 2709)

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

A01	`01`	`1`		`@0 0302-9743`
A05				`@2 1684`
A08	`01`	`1`	`ENG`	`@1 On maximal repetitions in words`
A09	`01`	`1`	`ENG`	`@1 FCT '99 : fundamentals of computation theory : Iasi, 30 August - 3 september 1999`
A11	`01`	`1`		`@1 KOLPAKOV (R.)`
A11	`02`	`1`		`@1 KUCHEROV (G.)`
A12	`01`	`1`		`@1 CIOBANU (Gabriel) @9 ed.`
A12	`02`	`1`		`@1 PAUN (Gheorghe) @9 ed.`
A14	`01`			`@1 French-Russian Institute for Informatics and Applied Mathematics, Moscow University @2 119899 Moscow @3 RUS @Z 1 aut.`
A14	`02`			`@1 LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101 @2 54602 Villers-lès-Nancy @3 FRA @Z 2 aut.`
A20				`@1 374-385`
A21				`@1 1999`
A23	`01`			`@0 ENG`
A26	`01`			`@0 3-540-66412-2`
A43	`01`			`@1 INIST @2 16343 @5 354000084584580310`
A44				`@0 0000 @1 © 1999 INIST-CNRS. All rights reserved.`
A45				`@0 1 p.1/4`
A47	`01`	`1`		`@0 99-0526090`
A60				`@1 P @2 C`
A61				`@0 A`
A64	`01`	`1`		`@0 Lecture notes in computer science`
A66	`01`			`@0 DEU`
C01	`01`		`ENG`	@0 A (fractional) repetition in a word w is a subword with the period of at most half of the subword length. We study maximal repetitions occurring in w, that is those for which any extended subword of w has a bigger period. The set of such repetitions represents in a compact way all repetitions in w. We first study maximal repetitions in Fibonacci words - we count their exact number, and estimate the sum of their exponents. These quantities turn out to be linearly-bounded in the length of the word. We then prove that the maximal number of maximal repetitions in general words (on arbitrary alphabet) of length n is linearly-bounded in n, and we mention some applications and consequences of this result.
C02	`01`	`X`		`@0 001D02A05`
C02	`02`	`X`		`@0 001D02A01`
C03	`01`	`X`	`FRE`	`@0 Répétition @5 01`
C03	`01`	`X`	`ENG`	`@0 Repetition @5 01`
C03	`01`	`X`	`SPA`	`@0 Repetición @5 01`
C03	`02`	`X`	`FRE`	`@0 Longueur mot @5 02`
C03	`02`	`X`	`ENG`	`@0 Word length @5 02`
C03	`02`	`X`	`SPA`	`@0 Longitud palabra @5 02`
C03	`03`	`X`	`FRE`	`@0 Temps linéaire @5 03`
C03	`03`	`X`	`ENG`	`@0 Linear time @5 03`
C03	`03`	`X`	`SPA`	`@0 Tiempo lineal @5 03`
C03	`04`	`X`	`FRE`	`@0 Algorithmique @5 04`
C03	`04`	`X`	`ENG`	`@0 Algorithmics @5 04`
C03	`04`	`X`	`SPA`	`@0 Algorítmica @5 04`
C03	`05`	`X`	`FRE`	`@0 Maximal repetition in word @4 INC @5 72`
C03	`06`	`X`	`FRE`	`@0 Mot Fibonacci @4 INC @5 73`
C03	`07`	`X`	`FRE`	`@0 Mot binaire @4 INC @5 74`
N21				`@1 340`

A30	`01`	`1`	`ENG`	`@1 Fundamentals of computation theory. International symposium @2 12 @3 Iasi ROM @4 1999-08-30`

Format Inist (serveur)

NO :	PASCAL 99-0526090 INIST
ET :	On maximal repetitions in words
AU :	KOLPAKOV (R.); KUCHEROV (G.); CIOBANU (Gabriel); PAUN (Gheorghe)
AF :	French-Russian Institute for Informatics and Applied Mathematics, Moscow University/119899 Moscow/Russie (1 aut.); LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101/54602 Villers-lès-Nancy/France (2 aut.)
DT :	Publication en série; Congrès; Niveau analytique
SO :	Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 1999; Vol. 1684; Pp. 374-385; Bibl. 1 p.1/4
LA :	Anglais
EA :	A (fractional) repetition in a word w is a subword with the period of at most half of the subword length. We study maximal repetitions occurring in w, that is those for which any extended subword of w has a bigger period. The set of such repetitions represents in a compact way all repetitions in w. We first study maximal repetitions in Fibonacci words - we count their exact number, and estimate the sum of their exponents. These quantities turn out to be linearly-bounded in the length of the word. We then prove that the maximal number of maximal repetitions in general words (on arbitrary alphabet) of length n is linearly-bounded in n, and we mention some applications and consequences of this result.
CC :	001D02A05; 001D02A01
FD :	Répétition; Longueur mot; Temps linéaire; Algorithmique; Maximal repetition in word; Mot Fibonacci; Mot binaire
ED :	Repetition; Word length; Linear time; Algorithmics
SD :	Repetición; Longitud palabra; Tiempo lineal; Algorítmica
LO :	INIST-16343.354000084584580310
ID :	99-0526090

Links to Exploration step

Pascal:99-0526090

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">On maximal repetitions in words </title>
<author><name sortKey="Kolpakov, R" sort="Kolpakov, R" uniqKey="Kolpakov R" first="R." last="Kolpakov">R. Kolpakov</name>
<affiliation><inist:fA14 i1="01"><s1>French-Russian Institute for Informatics and Applied Mathematics, Moscow University</s1>
<s2>119899 Moscow</s2>
<s3>RUS</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Kucherov, G" sort="Kucherov, G" uniqKey="Kucherov G" first="G." last="Kucherov">G. Kucherov</name>
<affiliation><inist:fA14 i1="02"><s1>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101</s1>
<s2>54602 Villers-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">99-0526090</idno>
<date when="1999">1999</date>
<idno type="stanalyst">PASCAL 99-0526090 INIST</idno>
<idno type="RBID">Pascal:99-0526090</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000A89</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">On maximal repetitions in words </title>
<author><name sortKey="Kolpakov, R" sort="Kolpakov, R" uniqKey="Kolpakov R" first="R." last="Kolpakov">R. Kolpakov</name>
<affiliation><inist:fA14 i1="01"><s1>French-Russian Institute for Informatics and Applied Mathematics, Moscow University</s1>
<s2>119899 Moscow</s2>
<s3>RUS</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Kucherov, G" sort="Kucherov, G" uniqKey="Kucherov G" first="G." last="Kucherov">G. Kucherov</name>
<affiliation><inist:fA14 i1="02"><s1>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
<imprint><date when="1999">1999</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithmics</term>
<term>Linear time</term>
<term>Repetition</term>
<term>Word length</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Répétition</term>
<term>Longueur mot</term>
<term>Temps linéaire</term>
<term>Algorithmique</term>
<term>Maximal repetition in word</term>
<term>Mot Fibonacci</term>
<term>Mot binaire</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">A (fractional) repetition in a word w is a subword with the period of at most half of the subword length. We study maximal repetitions occurring in w, that is those for which any extended subword of w has a bigger period. The set of such repetitions represents in a compact way all repetitions in w. We first study maximal repetitions in Fibonacci words - we count their exact number, and estimate the sum of their exponents. These quantities turn out to be linearly-bounded in the length of the word. We then prove that the maximal number of maximal repetitions in general words (on arbitrary alphabet) of length n is linearly-bounded in n, and we mention some applications and consequences of this result.</div>
</front>
</TEI>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0302-9743</s0>
</fA01>
<fA05><s2>1684</s2>
</fA05>
<fA08 i1="01" i2="1" l="ENG"><s1>On maximal repetitions in words </s1>
</fA08>
<fA09 i1="01" i2="1" l="ENG"><s1>FCT '99 : fundamentals of computation theory : Iasi, 30 August - 3 september 1999</s1>
</fA09>
<fA11 i1="01" i2="1"><s1>KOLPAKOV (R.)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>KUCHEROV (G.)</s1>
</fA11>
<fA12 i1="01" i2="1"><s1>CIOBANU (Gabriel)</s1>
<s9>ed.</s9>
</fA12>
<fA12 i1="02" i2="1"><s1>PAUN (Gheorghe)</s1>
<s9>ed.</s9>
</fA12>
<fA14 i1="01"><s1>French-Russian Institute for Informatics and Applied Mathematics, Moscow University</s1>
<s2>119899 Moscow</s2>
<s3>RUS</s3>
<sZ>1 aut.</sZ>
</fA14>
<fA14 i1="02"><s1>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101</s1>
<s2>54602 Villers-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</fA14>
<fA20><s1>374-385</s1>
</fA20>
<fA21><s1>1999</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA26 i1="01"><s0>3-540-66412-2</s0>
</fA26>
<fA43 i1="01"><s1>INIST</s1>
<s2>16343</s2>
<s5>354000084584580310</s5>
</fA43>
<fA44><s0>0000</s0>
<s1>© 1999 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45><s0>1 p.1/4</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>99-0526090</s0>
</fA47>
<fA60><s1>P</s1>
<s2>C</s2>
</fA60>
<fA61><s0>A</s0>
</fA61>
<fA64 i1="01" i2="1"><s0>Lecture notes in computer science</s0>
</fA64>
<fA66 i1="01"><s0>DEU</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>A (fractional) repetition in a word w is a subword with the period of at most half of the subword length. We study maximal repetitions occurring in w, that is those for which any extended subword of w has a bigger period. The set of such repetitions represents in a compact way all repetitions in w. We first study maximal repetitions in Fibonacci words - we count their exact number, and estimate the sum of their exponents. These quantities turn out to be linearly-bounded in the length of the word. We then prove that the maximal number of maximal repetitions in general words (on arbitrary alphabet) of length n is linearly-bounded in n, and we mention some applications and consequences of this result.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001D02A05</s0>
</fC02>
<fC02 i1="02" i2="X"><s0>001D02A01</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE"><s0>Répétition</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG"><s0>Repetition</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA"><s0>Repetición</s0>
<s5>01</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE"><s0>Longueur mot</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG"><s0>Word length</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA"><s0>Longitud palabra</s0>
<s5>02</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE"><s0>Temps linéaire</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG"><s0>Linear time</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA"><s0>Tiempo lineal</s0>
<s5>03</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE"><s0>Algorithmique</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG"><s0>Algorithmics</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA"><s0>Algorítmica</s0>
<s5>04</s5>
</fC03>
<fC03 i1="05" i2="X" l="FRE"><s0>Maximal repetition in word</s0>
<s4>INC</s4>
<s5>72</s5>
</fC03>
<fC03 i1="06" i2="X" l="FRE"><s0>Mot Fibonacci</s0>
<s4>INC</s4>
<s5>73</s5>
</fC03>
<fC03 i1="07" i2="X" l="FRE"><s0>Mot binaire</s0>
<s4>INC</s4>
<s5>74</s5>
</fC03>
<fN21><s1>340</s1>
</fN21>
</pA>
<pR><fA30 i1="01" i2="1" l="ENG"><s1>Fundamentals of computation theory. International symposium</s1>
<s2>12</s2>
<s3>Iasi ROM</s3>
<s4>1999-08-30</s4>
</fA30>
</pR>
</standard>
<server><NO>PASCAL 99-0526090 INIST</NO>
<ET>On maximal repetitions in words</ET>
<AU>KOLPAKOV (R.); KUCHEROV (G.); CIOBANU (Gabriel); PAUN (Gheorghe)</AU>
<AF>French-Russian Institute for Informatics and Applied Mathematics, Moscow University/119899 Moscow/Russie (1 aut.); LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101/54602 Villers-lès-Nancy/France (2 aut.)</AF>
<DT>Publication en série; Congrès; Niveau analytique</DT>
<SO>Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 1999; Vol. 1684; Pp. 374-385; Bibl. 1 p.1/4</SO>
<LA>Anglais</LA>
<EA>A (fractional) repetition in a word w is a subword with the period of at most half of the subword length. We study maximal repetitions occurring in w, that is those for which any extended subword of w has a bigger period. The set of such repetitions represents in a compact way all repetitions in w. We first study maximal repetitions in Fibonacci words - we count their exact number, and estimate the sum of their exponents. These quantities turn out to be linearly-bounded in the length of the word. We then prove that the maximal number of maximal repetitions in general words (on arbitrary alphabet) of length n is linearly-bounded in n, and we mention some applications and consequences of this result.</EA>
<CC>001D02A05; 001D02A01</CC>
<FD>Répétition; Longueur mot; Temps linéaire; Algorithmique; Maximal repetition in word; Mot Fibonacci; Mot binaire</FD>
<ED>Repetition; Word length; Linear time; Algorithmics</ED>
<SD>Repetición; Longitud palabra; Tiempo lineal; Algorítmica</SD>
<LO>INIST-16343.354000084584580310</LO>
<ID>99-0526090</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 000A89 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000A89 | 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:99-0526090
   |texte=   On maximal repetitions in words 
}}

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

On maximal repetitions in words

On maximal repetitions in words

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