Quasiperiodicity and string covering
Identifieur interne : 000312 ( Istex/Corpus ); précédent : 000311; suivant : 000313Quasiperiodicity and string covering
Auteurs : Costas S. Iliopoulos ; Laurent MouchardSource :
- Theoretical Computer Science [ 0304-3975 ] ; 1999.
English descriptors
- KwdEn :
- Abaaba, Algorithm, Appropriate factor, Computer science, Concatenation, Easy seed, Easy seeds, Ehrenfeucht algorithm, Elsevier science, Failure function, Formal language theory, Hard seed, Hard seeds, Iliopoulos, Lecture notes, Local period, Longest span, Main steps, Maximal quasiperiodic factors, Mouchardl, Optimal algorithm, Parallel string, Periodic words, Periodicity, Proper factor, Quasiperiodic, Quasiperiodic factor, Quasiperiodicity, Quasiperiodicity problem, Regularity, Right extension, Superposition, Wide area.
- Teeft :
- Abaaba, Algorithm, Appropriate factor, Computer science, Concatenation, Easy seed, Easy seeds, Ehrenfeucht algorithm, Elsevier science, Failure function, Formal language theory, Hard seed, Hard seeds, Iliopoulos, Lecture notes, Local period, Longest span, Main steps, Maximal quasiperiodic factors, Mouchardl, Optimal algorithm, Parallel string, Periodic words, Periodicity, Proper factor, Quasiperiodic, Quasiperiodic factor, Quasiperiodicity, Quasiperiodicity problem, Regularity, Right extension, Superposition, Wide area.
Abstract
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.
Url:
DOI: 10.1016/S0304-3975(98)00260-6
Links to Exploration step
ISTEX:10737BF78BD626F99E6C0CB224A3C20D46D86E87Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Quasiperiodicity and string covering</title><author><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name><affiliation><mods:affiliation>Deptartment of Computer Science, King's College London, Strand, London, WC2R 2LS, UK</mods:affiliation></affiliation><affiliation><mods:affiliation>School of Computing, Curtin University of Technology, GPO Box U1987, Perth 6845, Western Australia Australia</mods:affiliation></affiliation></author><author><name sortKey="Mouchard, Laurent" sort="Mouchard, Laurent" uniqKey="Mouchard L" first="Laurent" last="Mouchard">Laurent Mouchard</name><affiliation><mods:affiliation>Corresponding author.</mods:affiliation></affiliation><affiliation><mods:affiliation>Deptartment of Computer Science, King's College London, Strand, London, WC2R 2LS, UK</mods:affiliation></affiliation><affiliation><mods:affiliation>LIR — ABISS, Université de Rouen, 76821 Mont Saint Aignan Cedex, France</mods:affiliation></affiliation><affiliation><mods:affiliation>2 Supported by the Conseil Régional de Haute Normandie.</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: lm@dir.univ-rouen.fr</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:10737BF78BD626F99E6C0CB224A3C20D46D86E87</idno><date when="1999" year="1999">1999</date><idno type="doi">10.1016/S0304-3975(98)00260-6</idno><idno type="url">https://api.istex.fr/document/10737BF78BD626F99E6C0CB224A3C20D46D86E87/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000312</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000312</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Quasiperiodicity and string covering</title><author><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name><affiliation><mods:affiliation>Deptartment of Computer Science, King's College London, Strand, London, WC2R 2LS, UK</mods:affiliation></affiliation><affiliation><mods:affiliation>School of Computing, Curtin University of Technology, GPO Box U1987, Perth 6845, Western Australia Australia</mods:affiliation></affiliation></author><author><name sortKey="Mouchard, Laurent" sort="Mouchard, Laurent" uniqKey="Mouchard L" first="Laurent" last="Mouchard">Laurent Mouchard</name><affiliation><mods:affiliation>Corresponding author.</mods:affiliation></affiliation><affiliation><mods:affiliation>Deptartment of Computer Science, King's College London, Strand, London, WC2R 2LS, UK</mods:affiliation></affiliation><affiliation><mods:affiliation>LIR — ABISS, Université de Rouen, 76821 Mont Saint Aignan Cedex, France</mods:affiliation></affiliation><affiliation><mods:affiliation>2 Supported by the Conseil Régional de Haute Normandie.</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: lm@dir.univ-rouen.fr</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Theoretical Computer Science</title><title level="j" type="abbrev">TCS</title><idno type="ISSN">0304-3975</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1999">1999</date><biblScope unit="volume">218</biblScope><biblScope unit="issue">1</biblScope><biblScope unit="page" from="205">205</biblScope><biblScope unit="page" to="216">216</biblScope></imprint><idno type="ISSN">0304-3975</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0304-3975</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Abaaba</term><term>Algorithm</term><term>Appropriate factor</term><term>Computer science</term><term>Concatenation</term><term>Easy seed</term><term>Easy seeds</term><term>Ehrenfeucht algorithm</term><term>Elsevier science</term><term>Failure function</term><term>Formal language theory</term><term>Hard seed</term><term>Hard seeds</term><term>Iliopoulos</term><term>Lecture notes</term><term>Local period</term><term>Longest span</term><term>Main steps</term><term>Maximal quasiperiodic factors</term><term>Mouchardl</term><term>Optimal algorithm</term><term>Parallel string</term><term>Periodic words</term><term>Periodicity</term><term>Proper factor</term><term>Quasiperiodic</term><term>Quasiperiodic factor</term><term>Quasiperiodicity</term><term>Quasiperiodicity problem</term><term>Regularity</term><term>Right extension</term><term>Superposition</term><term>Wide area</term></keywords><keywords scheme="Teeft" xml:lang="en"><term>Abaaba</term><term>Algorithm</term><term>Appropriate factor</term><term>Computer science</term><term>Concatenation</term><term>Easy seed</term><term>Easy seeds</term><term>Ehrenfeucht algorithm</term><term>Elsevier science</term><term>Failure function</term><term>Formal language theory</term><term>Hard seed</term><term>Hard seeds</term><term>Iliopoulos</term><term>Lecture notes</term><term>Local period</term><term>Longest span</term><term>Main steps</term><term>Maximal quasiperiodic factors</term><term>Mouchardl</term><term>Optimal algorithm</term><term>Parallel string</term><term>Periodic words</term><term>Periodicity</term><term>Proper factor</term><term>Quasiperiodic</term><term>Quasiperiodic factor</term><term>Quasiperiodicity</term><term>Quasiperiodicity problem</term><term>Regularity</term><term>Right extension</term><term>Superposition</term><term>Wide area</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">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.</div></front></TEI><istex><corpusName>elsevier</corpusName><keywords><teeft><json:string>concatenation</json:string><json:string>quasiperiodicity</json:string><json:string>iliopoulos</json:string><json:string>quasiperiodic</json:string><json:string>computer science</json:string><json:string>algorithm</json:string><json:string>hard seed</json:string><json:string>mouchardl</json:string><json:string>abaaba</json:string><json:string>periodic words</json:string><json:string>superposition</json:string><json:string>periodicity</json:string><json:string>hard seeds</json:string><json:string>local period</json:string><json:string>right extension</json:string><json:string>easy seeds</json:string><json:string>longest span</json:string><json:string>easy seed</json:string><json:string>maximal quasiperiodic factors</json:string><json:string>optimal algorithm</json:string><json:string>quasiperiodic factor</json:string><json:string>main steps</json:string><json:string>ehrenfeucht algorithm</json:string><json:string>formal language theory</json:string><json:string>appropriate factor</json:string><json:string>elsevier science</json:string><json:string>lecture notes</json:string><json:string>failure function</json:string><json:string>quasiperiodicity problem</json:string><json:string>wide area</json:string><json:string>parallel string</json:string><json:string>proper factor</json:string><json:string>regularity</json:string></teeft></keywords><author><json:item><name>Costas S. Iliopoulos</name><affiliations><json:string>Deptartment of Computer Science, King's College London, Strand, London, WC2R 2LS, UK</json:string><json:string>School of Computing, Curtin University of Technology, GPO Box U1987, Perth 6845, Western Australia Australia</json:string></affiliations></json:item><json:item><name>Laurent Mouchard</name><affiliations><json:string>Corresponding author.</json:string><json:string>Deptartment of Computer Science, King's College London, Strand, London, WC2R 2LS, UK</json:string><json:string>LIR — ABISS, Université de Rouen, 76821 Mont Saint Aignan Cedex, France</json:string><json:string>2 Supported by the Conseil Régional de Haute Normandie.</json:string><json:string>E-mail: lm@dir.univ-rouen.fr</json:string></affiliations></json:item></author><subject><json:item><lang><json:string>eng</json:string></lang><value>Regularities</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Periodicity</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Quasiperiodicity</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Covers</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Seeds</value></json:item></subject><arkIstex>ark:/67375/6H6-NMRDP3B1-M</arkIstex><language><json:string>eng</json:string></language><originalGenre><json:string>Full-length article</json:string></originalGenre><abstract>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.</abstract><qualityIndicators><score>7.143</score><pdfWordCount>4099</pdfWordCount><pdfCharCount>22127</pdfCharCount><pdfVersion>1.2</pdfVersion><pdfPageCount>12</pdfPageCount><pdfPageSize>468 x 684 pts</pdfPageSize><refBibsNative>true</refBibsNative><abstractWordCount>87</abstractWordCount><abstractCharCount>534</abstractCharCount><keywordCount>5</keywordCount></qualityIndicators><title>Quasiperiodicity and string covering</title><pii><json:string>S0304-3975(98)00260-6</json:string></pii><genre><json:string>research-article</json:string></genre><serie><title>Thèse</title><language><json:string>unknown</json:string></language></serie><host><title>Theoretical Computer Science</title><language><json:string>unknown</json:string></language><publicationDate>1999</publicationDate><issn><json:string>0304-3975</json:string></issn><pii><json:string>S0304-3975(00)X0107-7</json:string></pii><volume>218</volume><issue>1</issue><pages><first>205</first><last>216</last></pages><genre><json:string>journal</json:string></genre></host><namedEntities><unitex><date><json:string>1999</json:string></date><geogName></geogName><orgName><json:string>Coding, Systems Theory</json:string><json:string>France Abstract In</json:string></orgName><orgName_funder></orgName_funder><orgName_provider></orgName_provider><persName><json:string>W. Build</json:string><json:string>C.S. Iliopoulos</json:string><json:string>C.S. Niopoulos</json:string><json:string>S. Iliopoulos</json:string><json:string>L. Mouchardl</json:string><json:string>L. MouchardlTheoretical</json:string><json:string>B. Example</json:string><json:string>Decomposition</json:string></persName><placeName><json:string>Australia</json:string><json:string>Periodicity</json:string><json:string>Quasiperiodicity</json:string><json:string>Perth</json:string><json:string>Saint Aignan</json:string></placeName><ref_url></ref_url><ref_bibl><json:string>[ 3,6,11]</json:string><json:string>[4]</json:string><json:string>[12]</json:string><json:string>Apostolico et al.</json:string><json:string>[6]</json:string><json:string>[16]</json:string><json:string>[3]</json:string><json:string>[20]</json:string><json:string>Iliopoulos et al. [13]</json:string><json:string>[5]</json:string><json:string>[15]</json:string><json:string>[7]</json:string><json:string>[14]</json:string><json:string>[9]</json:string><json:string>[2]</json:string><json:string>[13]</json:string></ref_bibl><bibl></bibl></unitex></namedEntities><ark><json:string>ark:/67375/6H6-NMRDP3B1-M</json:string></ark><categories><wos><json:string>1 - science</json:string><json:string>2 - computer science, theory & methods</json:string></wos><scienceMetrix><json:string>1 - applied sciences</json:string><json:string>2 - information & communication technologies</json:string><json:string>3 - computation theory & mathematics</json:string></scienceMetrix><scopus><json:string>1 - Physical Sciences</json:string><json:string>2 - Computer Science</json:string><json:string>3 - General Computer Science</json:string><json:string>1 - Physical Sciences</json:string><json:string>2 - Mathematics</json:string><json:string>3 - Theoretical Computer Science</json:string></scopus><inist><json:string>1 - sciences appliquees, technologies et medecines</json:string><json:string>2 - sciences exactes et technologie</json:string><json:string>3 - sciences et techniques communes</json:string><json:string>4 - mathematiques</json:string></inist></categories><publicationDate>1999</publicationDate><copyrightDate>1999</copyrightDate><doi><json:string>10.1016/S0304-3975(98)00260-6</json:string></doi><id>10737BF78BD626F99E6C0CB224A3C20D46D86E87</id><score>1</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/10737BF78BD626F99E6C0CB224A3C20D46D86E87/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/10737BF78BD626F99E6C0CB224A3C20D46D86E87/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/10737BF78BD626F99E6C0CB224A3C20D46D86E87/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a">Quasiperiodicity and string covering</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>ELSEVIER</publisher><availability><p>ELSEVIER</p></availability><date>1999</date></publicationStmt><notesStmt><note>Partially supported by EPSRC grant GR/J 17844.</note><note type="content">Section title: Algorithmic on word</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a">Quasiperiodicity and string covering</title><author xml:id="author-0000"><persName><forename type="first">Costas S.</forename><surname>Iliopoulos</surname></persName><affiliation>Deptartment of Computer Science, King's College London, Strand, London, WC2R 2LS, UK</affiliation><affiliation>School of Computing, Curtin University of Technology, GPO Box U1987, Perth 6845, Western Australia Australia</affiliation></author><author xml:id="author-0001"><persName><forename type="first">Laurent</forename><surname>Mouchard</surname></persName><email>lm@dir.univ-rouen.fr</email><affiliation>Corresponding author.</affiliation><affiliation>Deptartment of Computer Science, King's College London, Strand, London, WC2R 2LS, UK</affiliation><affiliation>LIR — ABISS, Université de Rouen, 76821 Mont Saint Aignan Cedex, France</affiliation><affiliation>2 Supported by the Conseil Régional de Haute Normandie.</affiliation></author><idno type="istex">10737BF78BD626F99E6C0CB224A3C20D46D86E87</idno><idno type="DOI">10.1016/S0304-3975(98)00260-6</idno><idno type="PII">S0304-3975(98)00260-6</idno></analytic><monogr><title level="j">Theoretical Computer Science</title><title level="j" type="abbrev">TCS</title><idno type="pISSN">0304-3975</idno><idno type="PII">S0304-3975(00)X0107-7</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1999"></date><biblScope unit="volume">218</biblScope><biblScope unit="issue">1</biblScope><biblScope unit="page" from="205">205</biblScope><biblScope unit="page" to="216">216</biblScope></imprint></monogr></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1999</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>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.</p></abstract><textClass><keywords scheme="keyword"><list><head>Keywords</head><item><term>Regularities</term></item><item><term>Periodicity</term></item><item><term>Quasiperiodicity</term></item><item><term>Covers</term></item><item><term>Seeds</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="1999">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/10737BF78BD626F99E6C0CB224A3C20D46D86E87/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Elsevier, elements deleted: tail"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"></istex:docType><istex:document><converted-article version="4.5.2" docsubtype="fla"><item-info><jid>TCS</jid><aid>98002606</aid><ce:pii>S0304-3975(98)00260-6</ce:pii><ce:doi>10.1016/S0304-3975(98)00260-6</ce:doi><ce:copyright type="unknown" year="1999"></ce:copyright></item-info><head><ce:article-footnote><ce:label>☆</ce:label><ce:note-para>Partially supported by EPSRC grant GR/J 17844.</ce:note-para></ce:article-footnote><ce:dochead><ce:textfn>Algorithmic on word</ce:textfn></ce:dochead><ce:title>Quasiperiodicity and string covering</ce:title><ce:author-group><ce:author><ce:given-name>Costas S.</ce:given-name><ce:surname>Iliopoulos</ce:surname><ce:cross-ref refid="AFF1"><ce:sup>a</ce:sup></ce:cross-ref><ce:cross-ref refid="AFF2"><ce:sup>b</ce:sup></ce:cross-ref></ce:author><ce:author><ce:given-name>Laurent</ce:given-name><ce:surname>Mouchard</ce:surname><ce:cross-ref refid="COR1"><ce:sup>∗</ce:sup></ce:cross-ref><ce:cross-ref refid="AFF1"><ce:sup>a</ce:sup></ce:cross-ref><ce:cross-ref refid="AFF3"><ce:sup>c</ce:sup></ce:cross-ref><ce:cross-ref refid="FN1"><ce:sup>2</ce:sup></ce:cross-ref><ce:e-address>lm@dir.univ-rouen.fr</ce:e-address></ce:author><ce:affiliation id="AFF1"><ce:label>a</ce:label><ce:textfn>Deptartment of Computer Science, King's College London, Strand, London, WC2R 2LS, UK</ce:textfn></ce:affiliation><ce:affiliation id="AFF2"><ce:label>b</ce:label><ce:textfn>School of Computing, Curtin University of Technology, GPO Box U1987, Perth 6845, Western Australia Australia</ce:textfn></ce:affiliation><ce:affiliation id="AFF3"><ce:label>c</ce:label><ce:textfn>LIR — ABISS, Université de Rouen, 76821 Mont Saint Aignan Cedex, France</ce:textfn></ce:affiliation><ce:correspondence id="COR1"><ce:label>∗</ce:label><ce:text>Corresponding author.</ce:text></ce:correspondence><ce:footnote id="FN1"><ce:label>2</ce:label><ce:note-para>Supported by the Conseil Régional de Haute Normandie.</ce:note-para></ce:footnote></ce:author-group><ce:abstract><ce:section-title>Abstract</ce:section-title><ce:abstract-sec><ce:simple-para>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.</ce:simple-para></ce:abstract-sec></ce:abstract><ce:keywords><ce:section-title>Keywords</ce:section-title><ce:keyword><ce:text>Regularities</ce:text></ce:keyword><ce:keyword><ce:text>Periodicity</ce:text></ce:keyword><ce:keyword><ce:text>Quasiperiodicity</ce:text></ce:keyword><ce:keyword><ce:text>Covers</ce:text></ce:keyword><ce:keyword><ce:text>Seeds</ce:text></ce:keyword></ce:keywords></head></converted-article></istex:document></istex:metadataXml><mods version="3.6"><titleInfo><title>Quasiperiodicity and string covering</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Quasiperiodicity and string covering</title></titleInfo><name type="personal"><namePart type="given">Costas S.</namePart><namePart type="family">Iliopoulos</namePart><affiliation>Deptartment of Computer Science, King's College London, Strand, London, WC2R 2LS, UK</affiliation><affiliation>School of Computing, Curtin University of Technology, GPO Box U1987, Perth 6845, Western Australia Australia</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Laurent</namePart><namePart type="family">Mouchard</namePart><affiliation>Corresponding author.</affiliation><affiliation>Deptartment of Computer Science, King's College London, Strand, London, WC2R 2LS, UK</affiliation><affiliation>LIR — ABISS, Université de Rouen, 76821 Mont Saint Aignan Cedex, France</affiliation><affiliation>2 Supported by the Conseil Régional de Haute Normandie.</affiliation><affiliation>E-mail: lm@dir.univ-rouen.fr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="Full-length article" authority="ISTEX" authorityURI="https://content-type.data.istex.fr" valueURI="https://content-type.data.istex.fr/ark:/67375/XTP-1JC4F85T-7">research-article</genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">1999</dateIssued><copyrightDate encoding="w3cdtf">1999</copyrightDate></originInfo><language><languageTerm type="code" authority="iso639-2b">eng</languageTerm><languageTerm type="code" authority="rfc3066">en</languageTerm></language><abstract lang="en">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.</abstract><note>Partially supported by EPSRC grant GR/J 17844.</note><note type="content">Section title: Algorithmic on word</note><subject><genre>Keywords</genre><topic>Regularities</topic><topic>Periodicity</topic><topic>Quasiperiodicity</topic><topic>Covers</topic><topic>Seeds</topic></subject><relatedItem type="host"><titleInfo><title>Theoretical Computer Science</title></titleInfo><titleInfo type="abbreviated"><title>TCS</title></titleInfo><genre type="journal" authority="ISTEX" authorityURI="https://publication-type.data.istex.fr" valueURI="https://publication-type.data.istex.fr/ark:/67375/JMC-0GLKJH51-B">journal</genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">19990428</dateIssued></originInfo><identifier type="ISSN">0304-3975</identifier><identifier type="PII">S0304-3975(00)X0107-7</identifier><part><date>19990428</date><detail type="volume"><number>218</number><caption>vol.</caption></detail><detail type="issue"><number>1</number><caption>no.</caption></detail><extent unit="issue-pages"><start>1</start><end>216</end></extent><extent unit="pages"><start>205</start><end>216</end></extent></part></relatedItem><identifier type="istex">10737BF78BD626F99E6C0CB224A3C20D46D86E87</identifier><identifier type="ark">ark:/67375/6H6-NMRDP3B1-M</identifier><identifier type="DOI">10.1016/S0304-3975(98)00260-6</identifier><identifier type="PII">S0304-3975(98)00260-6</identifier><recordInfo><recordContentSource authority="ISTEX" authorityURI="https://loaded-corpus.data.istex.fr" valueURI="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-HKKZVM7B-M">elsevier</recordContentSource></recordInfo></mods><json:item><extension>json</extension><original>false</original><mimetype>application/json</mimetype><uri>https://api.istex.fr/document/10737BF78BD626F99E6C0CB224A3C20D46D86E87/metadata/json</uri></json:item></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000312 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 000312 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Asie
|area= AustralieFrV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:10737BF78BD626F99E6C0CB224A3C20D46D86E87
|texte= Quasiperiodicity and string covering
}}
| This area was generated with Dilib version V0.6.33. |  |