Combinatorial queries and updates on partial words

Adrian Diaconu, Florin Manea, Cǎtǎlin Tiseanu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

In this paper we define four combinatorial queries on partial words, asking if a factor of a partial word is a k-repetition, k-free, overlap-free, and primitive, respectively. We show how a given partial word can be preprocessed efficiently in order to answer each of these queries in constant time. Also, we define an update operation for partial words: add a new symbol at the rightmost end of a given partial word; further, we show that the data structures obtained during the preprocessing mentioned above can be updated efficiently in order to still be able to answer all the combinatorial queries, for the updated word, in constant time.

Original languageEnglish (US)
Title of host publicationFundamentals of Computation Theory - 17th International Symposium, FCT 2009, Proceedings
Pages96-108
Number of pages13
DOIs
StatePublished - Nov 9 2009
Externally publishedYes
Event17th International Symposium on Fundamentals of Computation Theory, FCT 2009 - Wroclaw, Poland
Duration: Sep 2 2009Sep 4 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5699 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other17th International Symposium on Fundamentals of Computation Theory, FCT 2009
CountryPoland
CityWroclaw
Period9/2/099/4/09

Fingerprint Dive into the research topics of 'Combinatorial queries and updates on partial words'. Together they form a unique fingerprint.

Cite this