About: A word [Formula: see text] is a scattered factor of a word w if u can be obtained from w by deleting some of its letters: there exist the (potentially empty) words [Formula: see text] such that [Formula: see text]. The set of all scattered factors up to length k of a word is called its full k-spectrum. Firstly, we show an algorithm deciding whether the k-spectra for given k of two words are equal or not, running in optimal time. Secondly, we consider a notion of scattered-factors universality: the word w, with [Formula: see text], is called k-universal if its k-spectrum includes all words of length k over the alphabet [Formula: see text]; we extend this notion to k-circular universality. After a series of preliminary combinatorial results, we present an algorithm computing, for a given [Formula: see text]-universal word w the minimal i such that [Formula: see text] is k-universal for some [Formula: see text]. Several other connected problems are also considered.

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: A word [Formula: see text] is a scattered factor of a word w if u can be obtained from w by deleting some of its letters: there exist the (potentially empty) words [Formula: see text] such that [Formula: see text]. The set of all scattered factors up to length k of a word is called its full k-spectrum. Firstly, we show an algorithm deciding whether the k-spectra for given k of two words are equal or not, running in optimal time. Secondly, we consider a notion of scattered-factors universality: the word w, with [Formula: see text], is called k-universal if its k-spectrum includes all words of length k over the alphabet [Formula: see text]; we extend this notion to k-circular universality. After a series of preliminary combinatorial results, we present an algorithm computing, for a given [Formula: see text]-universal word w the minimal i such that [Formula: see text] is k-universal for some [Formula: see text]. Several other connected problems are also considered. Goto Sponge NotDistinct Permalink

An Entity of Type : fabio:Abstract, within Data Space : wasabi.inria.fr associated with source document(s)

Attributes	Values
type	abstract
value	A word [Formula: see text] is a scattered factor of a word w if u can be obtained from w by deleting some of its letters: there exist the (potentially empty) words [Formula: see text] such that [Formula: see text]. The set of all scattered factors up to length k of a word is called its full k-spectrum. Firstly, we show an algorithm deciding whether the k-spectra for given k of two words are equal or not, running in optimal time. Secondly, we consider a notion of scattered-factors universality: the word w, with [Formula: see text], is called k-universal if its k-spectrum includes all words of length k over the alphabet [Formula: see text]; we extend this notion to k-circular universality. After a series of preliminary combinatorial results, we present an algorithm computing, for a given [Formula: see text]-universal word w the minimal i such that [Formula: see text] is k-universal for some [Formula: see text]. Several other connected problems are also considered.
subject	Algorithms Computing Mathematical logic Theoretical computer science Computational complexity theory »more»
part of	Scattered Factor-Universality of Words
is abstract of	Scattered Factor-Universality of Words
is hasSource of	covid:ann/target/f4cd768817d5cad4ae9087ff294b659626dda1b5 covid:ann/target/d3b69608bc3a222c9bccca58967fef504a7d3d6e covid:ann/target/0251d3435ebfda9c2fc152b6496a3f02be122e0e covid:ann/target/a0b5cd2264a1a0ed2525c0e0392e949c83d7cb4f covid:ann/target/d489dbc139fbd41a31e81ad05d4382a51c8ea344 »more»

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software