Questions tagged [reference-request]
Questions requesting papers in the literature on specific, narrow issues.
999
questions
0
votes
0
answers
23
views
Problems in $DTIME(n\log n)$ [closed]
Let $DTIME(t(n))$ denote the complexity class of languages solvable in time $O(t(n))$ by a deteministic Turing machine with one tape. By the result of Kobayashi, we know that $DTIME(o(n\log n))=REG$. ...
- 101
1
vote
0
answers
27
views
What is the type of a type signature?
For example, using GHCi,
ghci> f x = x + 1
ghci> :t f
f :: Num a => a -> a
What is the type of the type signature ...
3
votes
0
answers
15
views
k-compact vectored I/O
I have a practical programming problem that I am struggling to find an optimal algorithm for, in part because I don't know what to call it. The problem concerns vectored I/O (scatter/gather).
Consider ...
0
votes
1
answer
27
views
A proof of the completeness of PLTL (Propositional Linear Temporal Logic)
In what paper(s), textbook(s), and/or classnote(s) can I find a detailed proof of the completeness of a certain proof system for PLTL (Propositional Linear Temporal Logic)?
- 207
0
votes
0
answers
29
views
How to make a GUI for first-order logic representation?
This idea blows my mind, I would appreciate for any guidance. In essence, the question is how a machine should work to transform any kind of formal logic into its graphical representation (e.g. ...
3
votes
0
answers
49
views
Reference request about equivalence of automata / regular expressions up-to a language
The most widely used notion of equivalence of regular expressions
$r_1$ and $r_2$, or finite state automata ${A}_1$ and ${A}_2$ resp., over an alphabet $\Sigma$, is to consider their languages: we can ...
- 8,258
2
votes
0
answers
36
views
Modified DPLL for 3-SAT by reducing to 2-SAT
In Boolean Satisfiability of CNF formulae we have $k$-SAT where each clause has at most $k$ literals. It is well known that $k$-SAT is polynomial time reducible to $3$-SAT. It is also well known that $...
- 135
0
votes
0
answers
9
views
Up-to-date status of the GHC STG?
Where can I read about the current status of the GHC STG?
The paper that I have is "Implementing Lazy Functional Languages on Stock Machine: the Spineless Tagless G-machine". For example, I ...
- 109
0
votes
0
answers
8
views
Resources to learn NLP
I am an undergraduate student in mathematics. I have a fair bit of experience with deep learning in computer vision research and am willing to dabble into NLP. I hope that things won't be very ...
1
vote
0
answers
23
views
Suggestion for tools/libraries for multi-output boolean circuit minimization?
I am interested in the following problem
Input: A boolean function F with n boolean inputs and m boolean outputs.
Output: A circuit C implementing F such that C has as few gates as possible.
The ...
1
vote
1
answer
43
views
Encoding "all-except" constraints in CNF
I am looking for an efficient CNF encoding of the following situation: I have sets of boolean literals $A = \{ a_1, \ldots, a_m \}$, $B = \{ b_1,\ldots, b_n \}$ and subsets $B_1, \ldots, B_m$, where ...
- 166
3
votes
1
answer
62
views
Building the minimal automaton from the syntactic monoid of a language
I'm studying the algebraic view of automata theory. One of the basic results is that the syntactic monoid of a language $L$ is the transition monoid $M(A)$ of the minimal automaton $A(L)$ accepting $L$...
- 448
0
votes
0
answers
8
views
State of the art construction of OBDDs
I have some Boolean functions represented by pretty big Boolean formulas and I need to build OBDDs from the formulas for further manipulation. How to do it is well known with textbook algorithms but I ...
- 448
3
votes
0
answers
60
views
Lights-out! on a hex grid with buttons on nodes and lights on faces
Consider a truncated hexagonal grid, with some hexagons lit up, such as the one shown below:
Here the red hexagons are lit up while the dark gray hexagons are not lit up. The grid has buttons (small ...
- 5,772
2
votes
1
answer
50
views
Determining the minimum number of edges to add to a graph to obtain a clique of size $k$
As part of a hobby project I stubmled into the following question which has me stumped:
Given an undirected graph $G = (V, E)$ and an integer $k$, what is that smallest number of edges that need to be ...
0
votes
1
answer
27
views
Thought experiment about two AIs involved in an infinite game
I came up with a thought experiment on the limits of artificial intelligence that I was hoping to get advice on how to solve as well as any recommendations for further reading that explain relevant ...
- 101
0
votes
1
answer
79
views
Weighted-Graph Datasets
I am searching for datasets to evaluate an algorithm designed for tasks such as node-classification (edge-prediction, etc.) on weighted and potentially directed graphs.
The Stanford Network Analysis ...
- 1
2
votes
1
answer
413
views
How is the input to a BROUWER algorithm done
The Brouwer fixpoint theorem states that any continuous mapping $f$, from a convex, compact set to itself will contain a fixpoint.
The Brouwer algorithm finds these (approximate) fixpoints. But how is ...
- 39
0
votes
0
answers
15
views
Reference request for formal proof on weak references and correctness of reference counting
For my next spare-time project, I intend to do a JSON codec with ability to manipulate data structure.
I intend to implement reference counting for my data structures, and a problem immediately shows ...
- 161
0
votes
1
answer
60
views
How can I find a Stable Diffusion program?
Well, I know that I'm going to ask too much.
So, I really want to ask you a totally (powerful (!)) free completely off-line code to generate prompt-based images like midjourney. I want to run with my ...
- 141
1
vote
1
answer
57
views
Best known deterministic algorithm for generation of any (non random) n-bit prime?
Sometimes we need some prime number with certain minimum size for modular algorithm.
For practical purposes we can precompute (using fast randomized algorithms) table of some primes for range which ...
- 265
2
votes
1
answer
47
views
Sieve of Eratosthenes for factorization: bitwise complexity?
As is well-known (and easy to prove), carrying out a sieve of Eratosthenes on the first $N$ integers takes a number of word operations in the order of $N \sum_{p\leq \sqrt{N}} 1/p \sim N \log \log N$, ...
- 241
1
vote
1
answer
32
views
Can equations be simplified with the help of a given set of equations?
There are many posts here and elsewhere asking for algorithms to simplify simple arithmetic expressions. For example, this question asks how to simplify the expression $axc + byc + ayc + bxc$. ...
18
votes
5
answers
3k
views
Regular languages that seem irregular
I'm trying to find examples of languages that don't seem regular, but are. A reference to where such examples may be found is also appreciated.
So far I've found two. One is $L_1=\{a^ku\,\,|\,\,u\in \{...
- 391
0
votes
0
answers
28
views
Power of regex extensions [duplicate]
It is well known that classical regexes recognize exactly regular languages. But in practice, many programming languages have extensions to the regex syntax which potentially broaden the field of ...
- 111
0
votes
1
answer
48
views
Looking for name of a priority queue data structure based on bit-boundary buckets
(Note: cross-listed on stack overflow: https://stackoverflow.com/questions/73362856/looking-for-name-of-a-priority-queue-data-structure-based-on-bit-boundary-bucket)
I'm looking for the name of a data ...
- 5,772
0
votes
2
answers
64
views
Tiling a simple polygon with hexagons
Let $T$ be a hexagonal tiling of the plane and assume we are given a simple polygon $P$ (we define $P$ as the union of the points on its boundary and its interior). The task is to find the subset of $...
- 1
0
votes
0
answers
13
views
Reference/notes for introduction to (von Neumann) architecture
I am interested in understanding what we mean by a von Neumann architecture and need something at a very introductory level. Does anyone know of any good and readable references or notes that will ...
- 101
0
votes
0
answers
119
views
Are there solutions available anywhere for Matt Bishop's Computer Security: Art and Science?
I have been reading Matt Bishop's great textbook Computer Security: Art and Science, but cannot find solutions to the exercises anywhere. Has anyone come across them before on their journey across the ...
- 99
0
votes
1
answer
107
views
Any-goal bidirectional A* pathfinding reference
I want to solve the problem of finding a shortest path on a directed weighted graph from a certain node to any of a specified set of destination nodes (preferably the closest one, but that's not that ...
- 121
1
vote
0
answers
92
views
What's the fastest algorithm for polynomial interpolation in finite field with prime order at points 1, 2, 3, ..., n?
Suppose we have finite field $\mathbb{F}_p$ with prime order $p$. Can we find polynomial in $\mathbb{F}_p[x]$ having given values $a_1, a_2, ... a_n$ at $x=1, 2, ..., n$ in less than $O(n^2)$ ...
- 265
2
votes
1
answer
98
views
Cellular automata on the Eisenstein integers?
Is there any cellular automaton on the Eisenstein integers? By this I mean that the triangles formed by the Eisenstein integers are considered as cells and each triangle has three neighbours plus ...
- 123
0
votes
0
answers
104
views
Solutions for "Operating Systems: Principles and Practice" by Anderson, Dahlin?
I'm self-teaching myself operating systems using the textbook "Operating Systems: Principles and Practice" by Anderson and Dahlin. I am solving the exercises but it would be really helpful ...
- 1
1
vote
0
answers
25
views
Reference for the formal definition of sigma protocol
I'm looking for a book that contains the formal definition of sigma protocol (something like: A sigma protocol for a relation $R$ and a challenge space $C$ is... that satisfies the properties of ...
- 11
3
votes
1
answer
295
views
Shannon's result that some Boolean functions require exponential circuits
In 1949 Shannon proved, using a non-constructive counting argument, that some boolean functions have exponential circuit complexity, see [1] and many texts on computational complexity. This result has ...
- 8,258
1
vote
0
answers
53
views
First piece of code in scientific papers
What is the first/oldest piece of source code shown in an scientific paper or journal? I am looking for source code of assembly or a high level programming language which was real (implemented) and ...
- 111
1
vote
0
answers
114
views
A total order of rectangles related to containment
Suppose you have a set of rectangles $R_1,\dots,R_n$ in the plane, each described by an upper left point $p_1 \in \mathbb R^2$ and a lower right point $p_2 \in \mathbb R^2$, all pairwise different.
...
- 111
6
votes
0
answers
39
views
How to find the minimum number of elements to distinguish several given sets?
Given $n$ distinct sets $S_1, S_2, \cdots, S_n$, how to find a set $X$ such that $X \cap S_1, X \cap S_2, \cdots, X \cap S_n$ are still distinct, and the size of $X$ is minimum?
For example, given $\{...
Acesrc
3
votes
0
answers
20
views
Is there a comprehensive list of complexity theoretic reductions from and to prime number factorization?
I am interested in the complexity theoretic equivalences of prime number factorization.
My interest stems from prime number factorization being one of the few candidates for NPI.
I am especially ...
- 131
1
vote
0
answers
34
views
Shortest path with vertex capacity
I have an undirected graph where each edge $e=\{u,v\}$ has a positive weight $w_{uv}$ and each vertex $v$ has a positive capacity $c_v$. There are two special vertices: a source vertex $s$ and a ...
- 1,026
2
votes
0
answers
42
views
Quantum Boolean SAT algorithm?
Is there a quantum SAT algorithm, a quantum analogue of the DPLL or CDCL algorithms?
Note: I'm not looking for the quantum analogue of the Boolean satisfiability problem (though that would be ...
- 145
1
vote
0
answers
16
views
Circuit class: constant depth, poly-size, bounded fan-in
I'm looking for the name of a certain circuit complexity class. It captures, to me, the idea of "shallow physically feasible circuits". I'm looking for the class of problems with:
Constant ...
- 816
1
vote
1
answer
46
views
What does type theory as a theory of inductive definitions mean?
Unfortunately copy/paste doesn't work for this paper Inductive Definitions and Type Theory, but here is a snippet.
The paper begins by stating:
The first sentence of the second paragraph says type ...
- 1,953
3
votes
1
answer
42
views
What is a program analysis technique for tracing assignments (mutations)?
I am looking to write a program analysis for Java programs that tracks assignments and is able to discern:
whether a class field (static or not) is read and where the read originated
whether a class ...
- 145
0
votes
0
answers
36
views
Optimal text/code formatting with alignment constraints
Formatting code or things like TeX have some interesting problems. For instance in auto-formatting code you want to use up as much line space as possible but not go over a certain limit if possible. ...
- 3,758
0
votes
0
answers
13
views
Textbook request for Linear Cellular Automata, if possible with an abstract algebraic approach
I am a final semester pure math undergrad, and I became interested in Linear Cellular Automatas.I became interested after reading Klaus Sutner's article. In the article, a little abstract algebra is ...
- 109
2
votes
0
answers
33
views
How to think in automata theory or some recommendations of resources related to this?
Recently, I find that automata theory is very useful in computer science, it is used in many fields, such as computer network, digital design, computer architecture and operating system, even we can ...
- 21
2
votes
0
answers
43
views
Fastest randomized algorithm for trace distance
Assume to have query access to the values $p(x)$, and $q(x)$ of two probability distributions over n elements $x \in X$, $|X|=n$.
That is, for a given $x\in X$ we pay constant time $O(1)$ to perform a ...
- 227
1
vote
1
answer
98
views
Request for Good Encyclopedic works of computer science
I attempt to find a few general encyclopedic works on computer science such that looking up relevant terminologies is easily available ready to hand. I'm not familiar with the whole picture of ...
- 19
6
votes
1
answer
511
views
Fast and compact data structure for dynamic graphs
A graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ may be represented in central memory as follows:
an associative array (hash table) $V$ gives for any $v\in \mathcal{V}$ the list of its neighbors $V[v]$...
- 613