Blocksequences of k-local words

DOI10.1007/978-3-030-67731-2_9MaRDI QIDQ831795zbMATH OpenOpenAlexFDO

Authors Pamela Fleischmann, Lukas Haschke, Florin Manea, Dirk Nowotka, Cedric Tsatia Tsida, Judith Wiedenbeck

Publication date 24 March 2022

Full work available at URL https://arxiv.org/abs/2008.03516

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: The locality of words is a relatively young structural complexity measure, introduced by Day et al. in 2017 in order to define classes of patterns with variables which can be matched in polynomial time. The main tool used to compute the locality of a word is called marking sequence: an ordering of the distinct letters occurring in the respective order. Once a marking sequence is defined, the letters of the word are marked in steps: in the ith marking step, all occurrences of the ith letter of the marking sequence are marked. As such, after each marking step, the word can be seen as a sequence of blocks of marked letters separated by blocks of non-marked letters. By keeping track of the evolution of the marked blocks of the word through the marking defined by a marking sequence, one defines the blocksequence of the respective marking sequence. We first show that the words sharing the same blocksequence are only loosely connected, so we consider the stronger notion of extended blocksequence, which stores additional information on the form of each single marked block. In this context, we present a series of combinatorial results for words sharing the extended blocksequence.

Recommendations

• A local Ramsey theory for block sequences
• Local periods and binary partial words: an algorithm
• Locally convex words and permutations
• Block locally Toeplitz sequences: construction and properties
• On block Behrend sequences
• The fixing block method in combinatorics on words
• Recurrence and periodicity in infinite words from local periods
• Block partitions of sequences
• Locally periodic versus globally periodic infinite words
• Block reversal on finite words

Cites work

• scientific article; zbMATH DE number 67610 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 7278096 (Why is no real title available?)
• Algorithms for learning regular expressions from positive data
• Extended regular expressions: succinctness and decidability
• Finding patterns common to a set of strings
• Graph and string parameters: connections between pathwidth, cutwidth and the locality number
• Injectivity of the Parikh matrix mappings revisited
• Linear work suffix array construction
• On the parameterised complexity of string morphism problems
• Pattern matching with variables: a multivariate complexity analysis
• Pattern matching with variables: fast algorithms and new hardness results
• Patterns with bounded treewidth
• Revisiting Shinohara's algorithm for computing descriptive patterns

Cited in

(1)

• Word-representable graphs from a word's perspective

This page was built for publication: Blocksequences of \(k\)-local words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q831795)