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.
176 questions
0
votes
0
answers
19
views
How to enumerate theories logically equivalent to natural deduction?
Natural deduction seems to generally be structured around the idea of (an/) introduction and elimination rules(s) for each logical symbol.
I heard that that was an attempt to capture the way humans ...
- 162
0
votes
0
answers
24
views
What is the fastest algorithm for generating all non-isomorphic unlabeled free trees for n-vertices, and also for caterpillar trees of n-vertices?
I'm aware of some algorithms for each problem such as the WROM algorithm for unlabeled free trees and the algorithm from this page for all caterpillar trees of n-vertices.
However, I haven't been able ...
1
vote
1
answer
76
views
Constraints on the order of program semantics given by an enumeration of turing-complete system programs
There are Turing-complete systems like Jot where every natural number can be mapped to a valid program. This results in a Gödel numbering.
Now, if the semantics of the programs were, say
...
- 203
0
votes
1
answer
42
views
Generating all unique (tape content, head position) possibilities for a Turing Machine
Assuming a single tape (which extends infinitely in both directions) Turing Machine,
If its head and tape contents start at position $0$ and the tape contents are only extended to the right, then it ...
- 203
0
votes
1
answer
27
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$ ...
- 162
0
votes
0
answers
17
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(...
- 195
5
votes
0
answers
93
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
25
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 \...
1
vote
0
answers
40
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
58
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 ...
- 919
1
vote
1
answer
279
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
177
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
81
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
193
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
70
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
127
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
36
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
85
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
100
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
71
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 ...
- 133
13
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 ...
- 306
0
votes
1
answer
158
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\\\\...
- 1
0
votes
1
answer
267
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 ...
- 1
2
votes
1
answer
97
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
35
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 ...
- 374
4
votes
0
answers
56
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
300
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
914
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
248
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
239
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
175
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
594
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
240
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
139
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
232
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 ...
- 309
-1
votes
1
answer
161
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 ...
- 375
1
vote
1
answer
312
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
59
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 ...
- 375
-1
votes
1
answer
92
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. ...
- 375
0
votes
0
answers
47
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
47
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
1k
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
418
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
91
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 ...
- 375
0
votes
1
answer
72
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
...
- 375
0
votes
2
answers
193
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 ...
- 375