Questions about sequences of symbols, sets thereof and their properties as well as uses.
3
votes
1answer
130 views
Longest substrings of common length with the same parity
Given two sequences $a$ and $b$, find largest $x$ such that in $a$ there is substring $A$ and substring $B$ in $b$ meeting those conditions:
length of both $A$ and $B$ is equal to $x$;
sum of ...
2
votes
1answer
13 views
Approximating unique string occurrences using a small, fixed amount of memory
Is there a small-memory way to estimate how many unique strings have been encountered without needing to know the strings themselves? The trick is that we only have a tiny amount of memory to track ...
1
vote
1answer
41 views
Convert given string to Palindrome with given substring
Given a String S1 and String S2. Convert string S1 to a palindrome string such S2 is a substring of that palindromic string. Only operation allowed on S1 is replacement of any character with any other ...
1
vote
1answer
17 views
Describing the Language of a grammar in set theoretic notation where the length of strings need to be remembered
I am not well versed in this topic so please pardon any ambiguous notation.
I am trying to describe the language of this grammar in set-theoretic notation.
The Grammar is given by:
$ S \rightarrow ...
1
vote
1answer
32 views
Designing a context free grammar for a language; When to use the empty string
$L= \{a^{2i}b^{j}vc^{j}(ac)^{i} | i,j \ge 0, v \in \{a,b\}^*\}$ over the alphabet $\Sigma = \{a,b,c\}$
How can a grammar be created from the language without the use of the empty string. Below is my ...
0
votes
1answer
10 views
A hangman variation: determining a string by guessing substrings contained in it
I came up with this Hangman variation, where you must figure out the hidden word by asking whether a string is a substring of this word. E.g. if the hidden word is "abracadabra" and I guess "cad" I ...
2
votes
1answer
30 views
longest sub-sequence in both directions
Given a character array A of size n, compute the length of a longest sub-sequence S of A such that, S read backward is also a sub-sequence of A.
Example: A = cabca
the sub-sequence S = abc is the ...
2
votes
1answer
38 views
Uniqueness of byte arrays
Consider the situation, when you're given M byte arrays of size N, and you need to check if all of them have unique content (so ...
1
vote
1answer
53 views
Find the number of strings in the language $(∅∅^∗ + ∅)$
Consider the language $L = \emptyset\emptyset^∗ + \emptyset$.
How many words does $L$ contain? Zero or one?
Note: $\emptyset^∗ =\{\epsilon\}$.
0
votes
1answer
53 views
Is it possible to add every word in a file to a set in $\mathrm{O}(n)$ time?
The Problem:
I am currently analyzing a simple program that takes a file of length $n$, splits it into its individual words (seperated by white space) and adds those words to a set:
...
1
vote
0answers
16 views
Estimated vs actual period in Two-Way string search
Both the original paper and all implementations I've seen of the Two Way string search algorithm estimate the period of the needle as $\max(|u|,|v|)$+1 (where $u$ and $v$ are the critical factors). ...
2
votes
1answer
28 views
Regular expression for capturing a “C-style” string
I have started to learn automata theory and languages. I am new to regular expressions.
As a use case in real world, I would like to construct a regular expression to accept a c-style string: ...
0
votes
0answers
29 views
Text alignment algorithm for word misspelling and rearrangement
I'm working on a project involving OCR, and I'm writing a post-processor using which the user corrects the OCR output using a text editor.
The OCR algorithm returns a list of "Detected Words", each ...
1
vote
0answers
30 views
Detect all distinct k-th powers in a string for all k ≥ 3
In string theory, the $k$-th power of a string $w$ is named as $w^k$, where $w^0$ is the empty string $\epsilon$ and $w^n$ is the concatenation of $w$ and $w^{n - 1}$ $(n \in \mathbb{N}^{+})$.
The ...
0
votes
0answers
13 views
Definition of string-generation for NFAs
I am new to automaton theory, and I am currently trying to think my way through the basic concepts. Since I come from a linguistics perspective, I find it helpful to think of automatons as string-...
2
votes
1answer
43 views
How does topic or tag suggestion algorithms work?
I know it's a keyword based search. But sites like Quora have some good suggesting algorithms where the algorithm understands the intent of question asked rather than just the keywords meanings.
For ...
5
votes
1answer
78 views
Permutation of words that have matched parentheses
Let $L$ denote the (context-free) language of matched parentheses over the alphabet $\Sigma$. Consider the following problem:
Input: words $x_1,\dots,x_n \in \Sigma^*$
Question: does there exist a ...
0
votes
0answers
27 views
Convert arbitrary length String representing a decimal number to another base
Hopefully this question is fairly straight forward. I need to convert a String representing a decimal number to another base 2^16. I have a way to store very large numbers and perform arithmetic on ...
2
votes
1answer
92 views
Finding the maximum substring for which a given predicate is true
Given a string $S$ of length $N$ and a string predicate $F$, find the maximum substring, $s$, such that $F(s) = \text{true}$. Assume that $F$ satisfies the following:
If $F(g) = \text{true}$, then ...
2
votes
1answer
49 views
String matching
I need to design a data structure to which I can efficiently add new words(Strings) and search for an existing word. Also, the search word can contain . in it which ...
2
votes
1answer
23 views
Minimum number of strings to cover entire space within Hamming distance
Given $(n, k)$:
What is the minimum number $x$ of (binary) strings such that all $n$-bit (binary) strings are within $k$ Hamming distance of some string?
Is there an asymptotic expansion or lower ...
2
votes
1answer
28 views
optimize string search on black-box function
Given a lower-bound predicate function which returns true if an input is greater than or equal to a constant string, what is the optimal way to search for the ...
1
vote
0answers
25 views
Reference request: Practical string algorithms
I think I have quite a good understanding of string algorithms. However, a couple of days ago, I came across this post: Find all pairs of strings in a set with Levenshtein distance < d
I was ...
3
votes
1answer
57 views
Merge a set of strings based on overlaps
I have a set of strings that are slices of a single, longer string. It is not guaranteed, however, that any two strings from this set must overlap: only that all of them together overlap. I want to ...
1
vote
1answer
60 views
Construct binary palindrome by repeated appending and trimming
I was reading an article on Construct binary palindrome by repeated appending and trimming. The problem is Given n and k, Construct a palindrome of size n using a binary number of size k repeating ...
5
votes
0answers
112 views
Partitioning through block moves to the end
Suppose we have a binary string $s$. We wish to partition this string in a series of $0$s followed by $1$s (alternatively: we wish to sort), using only one operation: moving three consecutive elements ...
0
votes
1answer
115 views
Complexity of Longest Palindromic Subsequence Algorithm
I'm trying to find the longest palindromic subsequence for any string and I've tried two approaches:
Recursive Algoritm
Dynamic Programming
Dynamic programming should be the better option in this ...
1
vote
1answer
115 views
Longest repeated substring
I am trying to solve a problem- Longest repeated substring in a string. Firstly, I built a suffix tree that takes O(n) time and then I traversed the suffix tree to find the deepest internal node. I am ...
1
vote
0answers
15 views
Pseudo-random regex-searchable function
Let $L$ be the set of strings of length $n$ (say $n=400$, for example). Let $N = \{0,1,\dots,|L|-1\}$. I am looking for a function $f : N \to L$ with the following properties:
$f$ is efficiently ...
2
votes
0answers
30 views
Minimization of simple cyclic automata
Version 1 of the question: I am looking for any correct $O(n)$ algorithm in the literature which will solve the DFA minimization problem referred to in the quote below from [Almeida & Zeitoun 2008]...
0
votes
0answers
38 views
Variable bytes (bit arrays) and flipping single bits?
My interest is strictly theoretical at this point, but ultimately applied.
Is there any problem, theoretically, with defining a byte with m bits, and flipping single bits to connote T/F for a given ...
2
votes
0answers
27 views
Bad character rule in the Apostolico–Giancarlo algorithm
In the paper "Tight bounds on the complexity of the Apostoliko-Giancarlo algorithm" by Crochemore and Lecroq authors prove that algorithm performs not more than $1.5n$ comparison of characters in the ...
5
votes
1answer
377 views
Find all substrings that fit the mask with asterisks
There is a problem.
Given string $text$ containing only letters and string $mask$ containing letters and asterisks (*), where asterisk means substitution of zero or more letters, find all substrings ...
3
votes
1answer
68 views
Can ropes (AVL trees) be interned?
Can AVL trees be interned for fast equality comparison? Is there work on interning data-structures or can you show that this cannot be done in better than $O(n)$ time?
I recently implemented a rope ...
2
votes
1answer
32 views
Methods, Routines, or Algorithms To Optimize Selection of String Compression Methods
When encoding a a 2D Datamatrix barcode, I want the smallest output size. There are means to encode a compressed a string using some methods like C40.
Reference:
Here's a reference: https://en....
0
votes
1answer
26 views
Test a bit substring function
How do we test the following function?
bits(bitstring, i, j)
which returns a copy of the substring from i to ...
3
votes
2answers
196 views
Count the unique subsequences
I'm trying to count the number of subsequences of a long string.
e.g. BANANA -> B, A, N, BA, BN, AA, NN, NA, BAN, BAA, BNA, BNN, ANA, AAA, NAN, NNA, etc
There's the horribly inefficient way, which ...
3
votes
1answer
72 views
Shortest Non-Subsequence String With Constant-Size Alphabet
Let $S[1..n] \in \Sigma^*$ be a string of $n$ symbols over the alphabet $\Sigma$ where $|\Sigma| \in \mathcal{O}(1)$. Determine a shortest string which cannot be obtained from $S$ by deleting some (...
1
vote
1answer
76 views
Filling a string with wildcards with minimum cost
You are given a string with wildcards, e.g. X***Y*Z. Your goal is to print an input string filling all the wildcards in the given string.
You are allowed to write data to the string in blocks of ...
1
vote
1answer
135 views
The set of all eventually periodic words is not Buchi Recognizable?
An $\omega$-word $s \in \Sigma^\omega$ is eventually periodic if it is of the form $s = uv^\omega$ for finite words $u, v \in \Sigma^*$.
I want to show that the set of all eventually periodic words ...
4
votes
1answer
194 views
Finding the smallest string that contains a given set of substrings
The algorithm I am looking for has the following requirements: Input is a set of strings. You are looking for a string containing all input strings. The resulting string should be as short as possible....
1
vote
1answer
39 views
Computing 'score' of string which preserves < relation
Is there a way to calculate some kind of numerical 'score' for arbitrary strings which when compared with score of some other string will preserve '<' relation?
I've searched for order preserving ...
-1
votes
1answer
16 views
Time Complexity of reconstructing corrupted file
Suppose all the spaces between the words(only small letter alphabets and no punctuation) in a file has been deleted and we need to reconstruct the file. There is a dictionary available which answers ...
0
votes
0answers
29 views
Suffix Trie with indexes of the last substring
As I understood there is a algorithm ("black box") that build trie from a string by O(n) time complexity, This algorithm use pointer to the first appearance of the substring in the string. Is the a ...
1
vote
2answers
52 views
Finding common structure in strings
I don't even know the right words to describe my problem, so I'll start with an example:
"aabaa", "ccrcc", "ffaff" are equivalent to some extent, because they all have the same length and follow the ...
0
votes
0answers
21 views
the question from this paper : Infinitary Equilibrium Logic and Strongly Equivalent Logic Programs
In the paper "Infinitary Equilibrium Logic and Strongly Equivalent Logic Programs", the authors claim:
The effect of adding (1) to a logic program describing $p$ and $q$ is, in general, not the ...
0
votes
2answers
369 views
Smallest length such that all substrings of that length contain at least 1 common character
Given a string, I have to return the smallest possible value of $k$ such that all of its sub-strings of length $k$ have at least one common character. Each sub-string must have the same common ...
1
vote
1answer
131 views
return all strings contains given string in suffix tree
Here is my question:
Given a compressed suffix tree of string S and a substring T.
I need to return all substrings of S that begins with the substring T
sorted by lexicographic order.
My approach:
I ...
0
votes
1answer
33 views
If all computations of non deterministic Turing machine on the input string are all accept then is the boolean formula of them a tautology?
If M is non deterministic Turing machine and w is any string then $\Phi_{M,w}$ is satisfiable if and only if M accepts w according to Cook and Levin (1971).
By the definition of non deterministic ...
-1
votes
1answer
67 views
Relating accepting/rejecting paths to satisfying/falsifying assignments in (Cook, 1971)
I read The Complexity of Theorem-Proving Procedures by Stephen A. Cook (1971).
Cook explains how to create a boolean formula $\Phi$ from $(M,w)$, where $M$ is a non-deterministic Turing machine that ...
