Questions tagged [enumeration]
This tag covers algorithms that enumerate some set, whether finite or infinite. Do not use it for questions about computability classes, such as recursively enumerable (RE) sets; use tags [computability] and [semi-decidability] for these.
173
questions
0
votes
1
answer
23
views
How can I estimate the time and cost (in relation to the machine and vocabulary) to enumerate sentences of English of n words?
I want to consider:
a vocabulary $V$ of $n$ distinct English words
a sequence of $m$ words, selected from $V$ (with repetition allowed)
a function $a$ which enumerates all unique sequences of $m$ ...
- 140
0
votes
0
answers
15
views
Finding program that enumerates a language using Von Neumman's computability paradigm
Given an alphabet $\Sigma$ of $n$ elements, whenever there is some order $\leq$ over the elements of $\Sigma$, we define $s^{\leq} : \Sigma^{*} \mapsto \Sigma^{*}$ as
\begin{align*}
s^{\leq} \left(...
- 181
5
votes
0
answers
75
views
Rank and unrank for Heap's Algorithm
I am looking for an unranking (and ranking) algorithm for permtuations that is consistent with the order that Heap's Algorithm generates permutations.
I have been researching a bit on ranking and ...
- 151
0
votes
1
answer
22
views
Enumerating proper intersections
Let
$U \subset \mathbb{N}$ be a finite universe set;
$B$ be a set of nonempty subsets of $U$ such that $B$ covers all elements in $U$, i.e. $\bigcup_{b \in B} b = U$, and if $b \in B$ then $b \...
0
votes
0
answers
27
views
Enumerate all n-tuples in parallel
Let $T = \{0, 1\} ^ {n}$, i.e. set of all $n$-bit binary strings ($n$-tuples). Let $f : T \to T$ be a function, that maps one string to another. $f$ is bijective, but $f^{-1}$ is hard to compute.
It ...
- 101
1
vote
0
answers
26
views
Code to list all maximal bicliques of a bipartite graph
We are looking for a code to list all maximal bicliques in bipartite graphs efficiently, as we want to run it on (large and sparse) graphs, with up to roughly a million nodes and edges in no more that ...
- 11
2
votes
1
answer
47
views
Looking for all "valid" combinations taken from a set of things, where subsets of "valid" things are always "valid"
I have a problem where I need to find all subsets of a set that satisfy some validity function. The function has the property that if a subset is invalid, so are all its supersets, and if a subset is ...
- 837
1
vote
1
answer
190
views
Enumerator for $L=\{0^{3^n}| n\ge 0\}$
I need to build an enumerator for $$L=\{0^{3^n}| n\ge 0\}, \Sigma = \{0\}, \Gamma = \{0, x, \sqcup\}$$ that has at most 10 states, including print and halt states. I can ignore the halt state and any ...
- 261
1
vote
1
answer
172
views
Iterating over combinations of 4 timestamps from 2 timelines *efficiently*
I need help in finding a more performant algorithm.
I have two timelines in the form of two indexed lists where each element is a floating-point value that represents seconds. The values in each list ...
- 11
0
votes
0
answers
78
views
Iterate through all values of a certain subset of all permutations
Let's say we've got $n$ numbers to multiply together. But the multiplication operation, like in computer floating-point arithmetics, is not associative. Thus the order of multiplication matters.
...
- 201
0
votes
1
answer
119
views
Given a list of strings enumerated over a finite alphabet, what's the most efficient way to get a string by its index?
Say you have the finite alphabet $\{a,b,c,d,e,f,g\}$ and an enumeration of finite strings over it by the shortlex order (length-lexicographic ordering), starting with the empty string, i.e.,
$\epsilon,...
- 1
1
vote
1
answer
63
views
Recreate a spanning tree in a grid graph given vertex descriptions
Let's assume I have graph above with spanning tree pointed out by blue edges.
Vertex at position (1,1) (row 1, column 1) is connected to the bottom vertex and has degree 1.
Vertex at position (4,2) (...
- 175
1
vote
1
answer
104
views
Enumerating through Turing Machines That Solve Same Problem
Is it possible to enumerate through all the Turing Machines that solve the same given problem? For example, we know that there exists a Turing Machine that finds a satisfying assignment given a 3SAT ...
- 11
0
votes
0
answers
35
views
Prove that a predicate is not computable
Prove that the following predicate is not computable:
$P_e(n) =
\begin{cases}
1 & \textrm{if } \phi_n(n) = e \\
0 & \textrm{otherwise}
\end{cases}$
Could someone explain how to approach ...
0
votes
0
answers
68
views
How can I generate all combinations of 2 sets of unique numbers? How are those called?
I want to generate 2 sets from N elements.
Sets must be unique in the combination of sets
Numbers must not repeat across the 2 sets
Sets can have any amount of numbers, but must not be empty
...
- 101
1
vote
1
answer
84
views
Is the following function computable? is it total?
I have the following function:
$f : N \to N $ and $f(n)= \max_{i \leq w(n)} g_{i}(n)$
with $g_1, g_2,...g_{w(n)}$ being an enumeration of all computable functions $g_i$, and $w : N \to N$ being any ...
- 53
2
votes
1
answer
61
views
Algorithm for finding subsets subject to union condition
I'm a mathematician and the following came up in my research:
Fix some positive integers $a_0,...,a_n$ and $N$.
Consider subsets $A_i \subset \{0,...,N\}$ where $|A_i|=a_i$, subject
to some fixed ...
- 123
12
votes
8
answers
3k
views
Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?
I wish there were more, but the subject pretty much captures my whole question.
Is there a non-Turing-complete model (some constrained term rewriting system or automaton or what have you) which is ...
- 296
0
votes
1
answer
122
views
Is set of all RE languages $\subseteq\\$ $\Sigma^{*}?$ [closed]
We know that any languages $\subseteq\\\\$ $\Sigma^{*}.$ Because any language collection of string over alphabet. And we know that set of all languages is $2^{\Sigma^{*}}$ which doesn't $\subsetneq\\\\...
- 317
0
votes
1
answer
247
views
Reduction from recursive language to recursive enumerable
If any language
$L_1$ reduces $L_2$ in polynomial time $L_1\leq_p^\mathsf{}L_2.$ If $L_1$ is recursive then $L_2$ is recursive and recursively enumerable, is it true? Because $L_2$ is at least as ...
- 317
2
votes
1
answer
91
views
Given a finite alphabet, how to generate all possible strings while excluding those that don't feature an element at least once?
Say you have the finite alphabet {a,b,c,d,e,f,g}. It's trivial to enumerate all strings of length <= 1000 over that set.
But what would be an efficient way of specifying a subset of those strings ...
- 23
1
vote
1
answer
33
views
Runtime of enumerating all integer vectors with a given sum where every element is greater than sqrt(k)
The problem of enumerating all lists of integers such that the list sums to a known value $k$ is well known and takes exponential time to compute.
If the problem is restricted so that the integers ...
- 364
4
votes
0
answers
52
views
Using graph symmetries to speed up subgraph enumeration
I have an undirected graph $G$. It has some symmetries in the sense that I know it's automorphism group $\text{Aut}(G)$. I am searching for a specific subgraph defined by some constraints $\phi$ and ...
-1
votes
1
answer
299
views
|L(M)| <= 330 is not computably enumerable
M is a turing machine description, L(M) is recognized by M, |L(M)| is the size of this language.
Why is {M : |L(M)| <= 330} not CE?
I can't seem to understand the logic why it is not CE, wouldn't ...
- 11
2
votes
2
answers
834
views
Is the union of computable enumerable sets computably enumerable
Let $\{A_n : n \in \mathbb{N}\}$ be a collection of c.e. (computably enumerable) sets. Is $\bigcup_n A_n$ c.e.?
That is, is the union of c.e. sets c.e.? Otherwise, under what conditions will this be ...
- 59
1
vote
2
answers
223
views
Show that a language is decidable iff some enumerator enumerates the language in decreasing order
Show that a language is decidable iff some enumerator enumerates the
language in decreasing order.
I know a language is decidable iff some enumerator enumerates the language in the standard string ...
- 47
1
vote
2
answers
220
views
What does an admissible numbering of computable functions look like?
I'm trying to understand how we can construct an admissible ordering of the computable (meaning, partial recursive) functions.
Initially my take on such an enumeration was from the point of view of an ...
- 133
2
votes
1
answer
47
views
Permuting integer vectors $x$ and $y$ which add to integer vector $z$
I posted this on mathoverflow but haven't recieved any comments. I wonder if there might be some insight from this community. Thanks!
The problem
Suppose you have nonnegative integer vectors of length ...
- 23
2
votes
2
answers
165
views
How to iterate the Hardy-Ramanujan integers quickly
The Hardy-Ramanujan integers, A025487 - OEIS, are integers which when factorized, have their exponents for all the primes starting from 2, in decreasing (not strictly) order. The first few terms are:
$...
- 313
1
vote
1
answer
453
views
Proof that languages are Turing-recognizable iff computably-enumerable
A very small question on this proof, which I found as Theorem 3.21 in Sipser's, and in my lecture notes.
In the "only if" direction, we assume that a Turing machine $M$ recognizes some ...
- 137
1
vote
1
answer
233
views
Enumerator for Word and Halting Problem
in theoretical computer science I learned for every recursive enumerable language there would be an enumerator and a grammar. So since word problem and halting problem are recursively enumerable, I ...
1
vote
1
answer
52
views
Why do we consider enumeration up to $\omega$ instead of leaving it to as many ordinal numbers?
A few minutes ago I asked a question about a "proof" that $\mathbb{R}$ is enumerable that crossed my mind: What's wrong with this "proof" that $\mathbb{R}$ is enumerable?
I was ...
- 157
0
votes
1
answer
129
views
What's wrong with this "proof" that $\mathbb{R}$ is enumerable?
The fake proof:
We know that $\mathbb{R}$ is uncountable, hence we cannot enumerate over it.
But what we do know is that $\mathbb{Q}$, the set of rationals, is countable, and even denumerable.
We ...
- 157
0
votes
0
answers
60
views
Finding index of $p_{k}$ element in the original sorted array if elements were to be removed using a specific condition
Consider a sorted list of numbers $C_{0}=\{0,1,2,3,...,n-1\}$ from where one element will be eliminated at each step. We are also given a value $L$ in $[0, 1)$ and let the indexing start from $0$.
...
- 19
0
votes
1
answer
217
views
How to define enumeration of the set of finite state machines?
I want to write a function that takes N (maximum number of states) as a parameter, enumerates all possible finite state machines up to N states, and returns random FSM with a probability in proportion ...
- 299
-1
votes
1
answer
155
views
Decide if a string is a member of a language that represents $P$?
For some enumeration of the complexity class P (such as this as an example: How does an enumerator for machines for languages work?), for each string 𝑝 in the enumeration, does there exist some other ...
- 345
1
vote
1
answer
295
views
Complexity of enumeration vs complexity of counting
I have a problem understanding the difference between complexity of enumeration and counting. We can solve every counting problem using enumeration algorithm.
Now, I have problem with the following. ...
- 57
0
votes
0
answers
57
views
Algorithm for enumerating over all possible pairs, by size (with some added conditions)?
Is there a way to enumerate, by size (the size of a pair is |𝑥|+|𝑦| but if the enumerator represents them in some different way than simply concatenating them (like via some different encoding) then ...
- 345
-1
votes
1
answer
86
views
Can enumeration take advantage of non-determinism?
If I want to build an NDTM to enumerate a list (of all Turing machines, for example) is there a way to use non-determinism to "speed this up" or take advantage of it somehow?
What types of of r.e. ...
- 345
0
votes
0
answers
43
views
Single-valued enumeration of all c.e. sets
Please help prove the following statement:
There exists a single-valued computable enumeration of the family of computably enumerable sets.
Definitions:
1) Let $S$ be nonempty countable set (...
- 19
1
vote
1
answer
125
views
Time complexity of a recursive enumeration in the problem of finding n-tuples of naturals greater than 1 with bounded product
I have to determine the time complexity of a recursive enumeration in the problem of finding n-tuples $(k_i, ..., k_n)$ of naturals greater than 1 with product less or equal to $K$. Problem can be ...
- 57
1
vote
0
answers
45
views
Can you verify a word's position in an enumeration faster than performing the enumeration?
Pt 1. Given as input the tuple: (word (from an r.e. language we fix), natural number)--does there exist a verifier, that runs faster than simply enumerating that language, that can accept if the word ...
user121977
2
votes
1
answer
939
views
How to enumerate all Turing machines?
Why is this true: “There are countably many Turing Machines”
In the top answer for this question a description of how to enumerate all Turing machines is given.
It all is clear except for one part: ...
user121977
2
votes
1
answer
371
views
How does an enumerator for machines for languages work?
In Dexter C. Kozen - Theory of Computation (2006, Springer) page 319 exercise 127 he says :
"A set of total recursive functions is recursively enumerable (r.e.) if there exists an r.e. set of indices ...
user121945
0
votes
1
answer
81
views
How do you represent an r.e. complexity class with a list of TMs?
In this book ‘Theory of computation’ By Dexter Kozen on page 313,exercise 127 he says "A set of total recursive functions is recursively enumerable (r.e.) if there exists an r.e. set of indices ...
- 345
0
votes
1
answer
67
views
Can a DTM simulate an enumerator E?
An enumerator is defined as a 7-tuple:
https://en.wikipedia.org/wiki/Enumerator_(computer_science)
A Deterministic Turing machine is defined as a 7-tuple:
https://en.wikipedia.org/wiki/Turing_machine
...
- 345
0
votes
2
answers
172
views
Enumeration of a class of languages
Can you enumerate a class of languages in such a way that the description of every language/ machine enumerated encodes where it was in the enumeration?
Ex:if you are given the description of the bth ...
- 345
1
vote
1
answer
132
views
Is co-P recursively enumerable?
P is RE, but is the complement of the class of languages decidable in polynomial time also recursively enumerable?
If both are RE then this makes P recursive?
- 345
1
vote
1
answer
216
views
Indexed family of all unary partial computable functions
Please help prove the following statement:
The indexed family of all unary partial computable functions that have total computable extension is computable.
Definitions:
Total function - a ...
- 19
2
votes
1
answer
35
views
Maximizing integer sets intersection (with integer delta)
There are two sets of integers with different numbers of items in them.
...
- 123