Quasiperiodicity and string covering
Identifieur interne :
006D71 ( PascalFrancis/Curation );
précédent :
006D70;
suivant :
006D72
Quasiperiodicity and string covering
Auteurs : C. S. Iliopoulos [
Royaume-Uni,
Australie] ;
L. Mouchard [
Royaume-Uni,
France]
Source :
-
Theoretical computer science [ 0304-3975 ] ; 1999.
RBID : Pascal:99-0409678
Descripteurs français
English descriptors
Abstract
In this paper, we study word regularities and in particular extensions of the notion of the word period: quasiperiodicity, covers and seeds. We present overviews of algorithms for computing the quasiperiodicity, the covers and the seeds of a given word. We also present an overview of an algorithm that finds maximal word factors with the above regularities. Finally, we show how Fine and Wilf's Theorem fails if we try to extend it directly to quasiperiodicity, as well as a new property on concatenation of periodic words.
pA |
A01 | 01 | 1 | | @0 0304-3975 |
---|
A02 | 01 | | | @0 TCSCDI |
---|
A03 | | 1 | | @0 Theor. comput. sci. |
---|
A05 | | | | @2 218 |
---|
A06 | | | | @2 1 |
---|
A08 | 01 | 1 | ENG | @1 Quasiperiodicity and string covering |
---|
A09 | 01 | 1 | ENG | @1 Words |
---|
A11 | 01 | 1 | | @1 ILIOPOULOS (C. S.) |
---|
A11 | 02 | 1 | | @1 MOUCHARD (L.) |
---|
A12 | 01 | 1 | | @1 NERAUD (J.) @9 ed. |
---|
A14 | 01 | | | @1 Deptartment of Computer Science. King's College London, Strand @2 London, WC2R 2LS @3 GBR @Z 1 aut. @Z 2 aut. |
---|
A14 | 02 | | | @1 School of Computing, Curtin University of Technology, GPO Box U1987 @2 Perth 6845, Western Australia @3 AUS @Z 1 aut. |
---|
A14 | 03 | | | @1 LIR - ABISS, Université de Rouen @2 76821 Mont Saint Aignan @3 FRA @Z 2 aut. |
---|
A20 | | | | @1 205-216 |
---|
A21 | | | | @1 1999 |
---|
A23 | 01 | | | @0 ENG |
---|
A43 | 01 | | | @1 INIST @2 17243 @5 354000084731350140 |
---|
A44 | | | | @0 0000 @1 © 1999 INIST-CNRS. All rights reserved. |
---|
A45 | | | | @0 20 ref. |
---|
A47 | 01 | 1 | | @0 99-0409678 |
---|
A60 | | | | @1 P @2 C |
---|
A61 | | | | @0 A |
---|
A64 | 01 | 1 | | @0 Theoretical computer science |
---|
A66 | 01 | | | @0 NLD |
---|
C01 | 01 | | ENG | @0 In this paper, we study word regularities and in particular extensions of the notion of the word period: quasiperiodicity, covers and seeds. We present overviews of algorithms for computing the quasiperiodicity, the covers and the seeds of a given word. We also present an overview of an algorithm that finds maximal word factors with the above regularities. Finally, we show how Fine and Wilf's Theorem fails if we try to extend it directly to quasiperiodicity, as well as a new property on concatenation of periodic words. |
---|
C02 | 01 | X | | @0 001D02B07B |
---|
C02 | 02 | X | | @0 001D02A02 |
---|
C03 | 01 | 3 | FRE | @0 Appariement chaîne @5 01 |
---|
C03 | 01 | 3 | ENG | @0 String matching @5 01 |
---|
C03 | 02 | X | FRE | @0 Régularité @5 02 |
---|
C03 | 02 | X | ENG | @0 Regularity @5 02 |
---|
C03 | 02 | X | SPA | @0 Regularidad @5 02 |
---|
C03 | 03 | X | FRE | @0 Variation quasi périodique @5 03 |
---|
C03 | 03 | X | ENG | @0 Quasi periodic variation @5 03 |
---|
C03 | 03 | X | SPA | @0 Variación semiperiódica @5 03 |
---|
C03 | 04 | X | FRE | @0 Théorie langage @5 04 |
---|
C03 | 04 | X | ENG | @0 Language theory @5 04 |
---|
C03 | 04 | X | SPA | @0 Teoría lenguaje @5 04 |
---|
C03 | 05 | X | FRE | @0 Langage formel @5 05 |
---|
C03 | 05 | X | ENG | @0 Formal language @5 05 |
---|
C03 | 05 | X | SPA | @0 Lenguaje formal @5 05 |
---|
N21 | | | | @1 263 |
---|
|
pR |
A30 | 01 | 1 | ENG | @1 "Words". International Conference @3 Rouen FRA @4 1997-09-22 |
---|
|
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: Pour aller vers cette notice dans l'étape Curation :006283
Links to Exploration step
Pascal:99-0409678
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Quasiperiodicity and string covering</title>
<author><name sortKey="Iliopoulos, C S" sort="Iliopoulos, C S" uniqKey="Iliopoulos C" first="C. S." last="Iliopoulos">C. S. Iliopoulos</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Deptartment of Computer Science. King's College London, Strand</s1>
<s2>London, WC2R 2LS</s2>
<s3>GBR</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Royaume-Uni</country>
</affiliation>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>School of Computing, Curtin University of Technology, GPO Box U1987</s1>
<s2>Perth 6845, Western Australia</s2>
<s3>AUS</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>Australie</country>
</affiliation>
</author>
<author><name sortKey="Mouchard, L" sort="Mouchard, L" uniqKey="Mouchard L" first="L." last="Mouchard">L. Mouchard</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Deptartment of Computer Science. King's College London, Strand</s1>
<s2>London, WC2R 2LS</s2>
<s3>GBR</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Royaume-Uni</country>
</affiliation>
<affiliation wicri:level="1"><inist:fA14 i1="03"><s1>LIR - ABISS, Université de Rouen</s1>
<s2>76821 Mont Saint Aignan</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">99-0409678</idno>
<date when="1999">1999</date>
<idno type="stanalyst">PASCAL 99-0409678 INIST</idno>
<idno type="RBID">Pascal:99-0409678</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">006283</idno>
<idno type="wicri:Area/PascalFrancis/Curation">006D71</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Quasiperiodicity and string covering</title>
<author><name sortKey="Iliopoulos, C S" sort="Iliopoulos, C S" uniqKey="Iliopoulos C" first="C. S." last="Iliopoulos">C. S. Iliopoulos</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Deptartment of Computer Science. King's College London, Strand</s1>
<s2>London, WC2R 2LS</s2>
<s3>GBR</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Royaume-Uni</country>
</affiliation>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>School of Computing, Curtin University of Technology, GPO Box U1987</s1>
<s2>Perth 6845, Western Australia</s2>
<s3>AUS</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>Australie</country>
</affiliation>
</author>
<author><name sortKey="Mouchard, L" sort="Mouchard, L" uniqKey="Mouchard L" first="L." last="Mouchard">L. Mouchard</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Deptartment of Computer Science. King's College London, Strand</s1>
<s2>London, WC2R 2LS</s2>
<s3>GBR</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Royaume-Uni</country>
</affiliation>
<affiliation wicri:level="1"><inist:fA14 i1="03"><s1>LIR - ABISS, Université de Rouen</s1>
<s2>76821 Mont Saint Aignan</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
</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="1999">1999</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>Formal language</term>
<term>Language theory</term>
<term>Quasi periodic variation</term>
<term>Regularity</term>
<term>String matching</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Appariement chaîne</term>
<term>Régularité</term>
<term>Variation quasi périodique</term>
<term>Théorie langage</term>
<term>Langage formel</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">In this paper, we study word regularities and in particular extensions of the notion of the word period: quasiperiodicity, covers and seeds. We present overviews of algorithms for computing the quasiperiodicity, the covers and the seeds of a given word. We also present an overview of an algorithm that finds maximal word factors with the above regularities. Finally, we show how Fine and Wilf's Theorem fails if we try to extend it directly to quasiperiodicity, as well as a new property on concatenation of periodic words.</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>218</s2>
</fA05>
<fA08 i1="01" i2="1" l="ENG"><s1>Quasiperiodicity and string covering</s1>
</fA08>
<fA09 i1="01" i2="1" l="ENG"><s1>Words</s1>
</fA09>
<fA11 i1="01" i2="1"><s1>ILIOPOULOS (C. S.)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>MOUCHARD (L.)</s1>
</fA11>
<fA12 i1="01" i2="1"><s1>NERAUD (J.)</s1>
<s9>ed.</s9>
</fA12>
<fA14 i1="01"><s1>Deptartment of Computer Science. King's College London, Strand</s1>
<s2>London, WC2R 2LS</s2>
<s3>GBR</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</fA14>
<fA14 i1="02"><s1>School of Computing, Curtin University of Technology, GPO Box U1987</s1>
<s2>Perth 6845, Western Australia</s2>
<s3>AUS</s3>
<sZ>1 aut.</sZ>
</fA14>
<fA14 i1="03"><s1>LIR - ABISS, Université de Rouen</s1>
<s2>76821 Mont Saint Aignan</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</fA14>
<fA20><s1>205-216</s1>
</fA20>
<fA21><s1>1999</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA43 i1="01"><s1>INIST</s1>
<s2>17243</s2>
<s5>354000084731350140</s5>
</fA43>
<fA44><s0>0000</s0>
<s1>© 1999 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45><s0>20 ref.</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>99-0409678</s0>
</fA47>
<fA60><s1>P</s1>
<s2>C</s2>
</fA60>
<fA64 i1="01" i2="1"><s0>Theoretical computer science</s0>
</fA64>
<fA66 i1="01"><s0>NLD</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>In this paper, we study word regularities and in particular extensions of the notion of the word period: quasiperiodicity, covers and seeds. We present overviews of algorithms for computing the quasiperiodicity, the covers and the seeds of a given word. We also present an overview of an algorithm that finds maximal word factors with the above regularities. Finally, we show how Fine and Wilf's Theorem fails if we try to extend it directly to quasiperiodicity, as well as a new property on concatenation of periodic words.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001D02B07B</s0>
</fC02>
<fC02 i1="02" i2="X"><s0>001D02A02</s0>
</fC02>
<fC03 i1="01" i2="3" l="FRE"><s0>Appariement chaîne</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="3" l="ENG"><s0>String matching</s0>
<s5>01</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE"><s0>Régularité</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG"><s0>Regularity</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA"><s0>Regularidad</s0>
<s5>02</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE"><s0>Variation quasi périodique</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG"><s0>Quasi periodic variation</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA"><s0>Variación semiperiódica</s0>
<s5>03</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE"><s0>Théorie langage</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG"><s0>Language theory</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA"><s0>Teoría lenguaje</s0>
<s5>04</s5>
</fC03>
<fC03 i1="05" i2="X" l="FRE"><s0>Langage formel</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="ENG"><s0>Formal language</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="SPA"><s0>Lenguaje formal</s0>
<s5>05</s5>
</fC03>
<fN21><s1>263</s1>
</fN21>
</pA>
<pR><fA30 i1="01" i2="1" l="ENG"><s1>"Words". International Conference</s1>
<s3>Rouen FRA</s3>
<s4>1997-09-22</s4>
</fA30>
</pR>
</standard>
</inist>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/PascalFrancis/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006D71 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Curation/biblio.hfd -nk 006D71 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Asie
|area= AustralieFrV1
|flux= PascalFrancis
|étape= Curation
|type= RBID
|clé= Pascal:99-0409678
|texte= Quasiperiodicity and string covering
}}
| This area was generated with Dilib version V0.6.33. Data generation: Tue Dec 5 10:43:12 2017. Site generation: Tue Mar 5 14:07:20 2024 | |