A new approach to regular \& indeterminate strings

DOI10.1016/J.TCS.2020.12.007MaRDI QIDQ2220865zbMATH OpenOpenAlexFDO

Authors Felipe A. Louza, Neerja Mhaskar, W. F. Smyth

Publication date 25 January 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

algorithmdegenerate stringgeneralized stringindeterminate stringManacher's conditionmaximal palindrome arraypalindromereverse engineeringstringologytransitive closure

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Abstract: In this paper we propose a new, more appropriate definition of regular and indeterminate strings. A regular string is one that is "isomorphic" to a string whose entries all consist of a single letter, but which nevertheless may itself include entries containing multiple letters. A string that is not regular is said to be indeterminate. We begin by proposing a new model for the representation of strings, regular or indeterminate, then go on to describe a linear time algorithm to determine whether or not a string $x=x[\mathrm{1..}n]$ is regular and, if so, to replace it by a lexicographically least (lex-least) string $y$ whose entries are all single letters. Furthermore, we connect the regularity of a string to the transitive closure problem on a graph, which in our special case can be efficiently solved. We then introduce the idea of a feasible palindrome array MP of a string, and prove that every feasible MP corresponds to some (regular or indeterminate) string. We describe an algorithm that constructs a string $x$ corresponding to given feasible MP, while ensuring that whenever possible $x$ is regular and if so, then lex-least. A final section outlines new research directions suggested by this changed perspective on regular and indeterminate strings.

Recommendations

• Indeterminate strings, prefix arrays \& undirected graphs
• Inferring an indeterminate string from a prefix graph
• Indeterminate string inference algorithms
• Computing covers using prefix tables
• Two-pattern strings. I: A recognition algorithm

Cites work

• A new approach to pattern matching in degenerate DNA/RNA sequences and distributed pattern matching
• A new approach to the periodicity lemma on strings with holes
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Algorithmic Combinatorics on Partial Words
• An adaptive hybrid pattern-matching algorithm on indeterminate strings
• Constructing an indeterminate string from its associated graph
• Fast pattern-matching on indeterminate strings
• Finite automata based algorithms on subsequences and supersequences of degenerate strings
• Generalized String Matching
• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• scientific article; zbMATH DE number 1874382 (Why is no real title available?)
• Indeterminate string inference algorithms
• Indeterminate strings, prefix arrays \& undirected graphs
• Inferring an indeterminate string from a prefix graph
• Introduction to algorithms
• Mathematical Foundations of Computer Science 2003
• Reconstructing a string from its Lyndon arrays
• Reverse engineering prefix tables

Cited in

(7)

• An umbral relation between pattern and commutation in strings
• Indeterminate string factorizations and degenerate text transformations
• scientific article; zbMATH DE number 6003273 (Why is no real title available?)
• A NON-STANDARD STRING EMBEDDING OF E₈
• Indeterminate strings, prefix arrays \& undirected graphs
• A unifying taxonomy of pattern matching in degenerate strings and founder graphs
• A new approach to the periodicity lemma on strings with holes

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: A new approach to regular \& indeterminate strings

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