Questions tagged [reference-request]
Questions requesting papers in the literature on specific, narrow issues.
1,023
questions
4
votes
0
answers
35
views
Prior or subsequent art for Microsoft COM’s “causality IDs”
Microsoft COM, in its object RPC part, had a peculiar mechanism that could be used to prohibit concurrent calls to the same object (or another object serviced by the same event loop) but permit ...
- 171
0
votes
0
answers
15
views
Current best output-sensitive algorithm for computing all maximal cliques of a graph
I am looking for a reference on the most optimal output-sensitive algorithm currently available for listing all maximal cliques in a graph.
I know the Bron-Kerbosch algorithm is highly utilized, but ...
1
vote
0
answers
24
views
Toda's theorem without $\oplus P$
Toda's theorem says that the polynomial time hierarchy is contained in $P^{\#P}$, the class of problems solvable by polynomial time oracle Turing machines with access to an oracle in #P, which is the ...
- 413
0
votes
0
answers
30
views
Articles and journals for undergrad students
I am searching for a CS equivalent to American Math Monthly. It should contain articles on topics and some problems at the end for submission. I need some recommendations .
Thanks in advance.
- 21
2
votes
1
answer
64
views
Is there any computation formalism based on general relativity?
Quantum mechanical principles have already been used to attack computer science problems in the form of quantum computing. In a similar vein, is there any usage of general relativity principles to ...
user33772
3
votes
1
answer
69
views
Division of Large Numbers with Known Factors
Consider two large numbers $a$ and $b$ of which some, not necessarily prime factors, are known. This means $a = a_1 \cdot \dots \cdot a_n$ and $b = b_1 \cdot \cdots \cdot b_m$. Required is their ...
- 151
0
votes
0
answers
22
views
Does lambda calculus become covariant if you fix the base type instead of the lambda calculus term?
In category theory, we are taught that polymorphic functions correspond to dinatural transformations, a k a multivariant natural transformations between functors of mixed variance
$\operatorname{G} \...
0
votes
0
answers
14
views
Looking for name of problem similar to Steiner trees but with an RGB balancing constraint (color code decoding)
In quantum computing, there is an error correcting code called the color code where each error in the bulk of the code produces three types of symptoms (one red, one green, one blue). Pairs of errors ...
- 5,802
0
votes
0
answers
16
views
Looking for collection of protocol state machines
I'm currently studying structural properties of network and control protocols and their relation to testing. I'm specifically interested in state machines. They would not need to cover the full ...
- 161
1
vote
1
answer
44
views
Memory efficient undo data structure
I was playing a puzzle game and started wondering how they implemented their undo feature. The game only has five possible moves, and only when the player does a move does the game state change, but ...
- 175
0
votes
0
answers
21
views
Reference and code for community discovery algorithms in multigraphs
In order to group unstructured or sem-structured texts for a timeline construction approach, I consider several types of correlations among such texts. These different correlations induce a weighted ...
- 101
0
votes
0
answers
13
views
Reference request for Unit Clause Based SAT Reduction Rules
I tested my XSAT solver using the 4 pigeons in 3 holes problem converted to XSAT. The pigeon hole instance I give below had 108 variables and 88 clauses after being converted to monotone XSAT. My ...
- 341
1
vote
0
answers
23
views
Resources on designing query languages
I'm looking for resources (books, papers, tutorials) on designing domain-specific query languages. I'm mostly interested in the design of syntax and grammar, rather than the implementation. Any UX-...
- 111
1
vote
2
answers
50
views
Estimating the number of elements shared in two sets using a random sample
Suppose we have two sets $A$ and $B$. The sets share some number of elements between them, but within each set, any item appears at most once. We want to determine how many elements they share in ...
- 837
2
votes
1
answer
43
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
0
votes
1
answer
75
views
On hardness of finding total dominating sets in triangle-free graphs
A total dominating set $S\subset V(G)$ is a set of vertices such that $\forall v\in V(G)$, $v$ has a neighbour in $S$. The minimum total dominating set of $G$ is a total dominating set of $G$ of ...
- 25
2
votes
1
answer
107
views
On hardness of finding dominating sets in triangle-free regular graphs
A $k$-regular graph is one in which every vertex has degree k. A triangle-free graph is one in which any three vertices do not form a triangle. A dominating set $D$ of a graph $G$ is a set of vertices ...
- 25
0
votes
1
answer
44
views
Introduction to theoretical computer science for research mathematicians
Are there any references on theoretical computer science aimed at people with a background in research mathematics?
For reference, I spend my time thinking about category theory and set theory most ...
- 101
1
vote
0
answers
177
views
Is there a proof of correctness for CPS translations into Appel's IR?
The IR given in Appel's book (Compiling with Continuations) is certainly well explored and battle-tested in production compilers. I have been able to find several works based on or inspired by it (...
- 711
1
vote
0
answers
30
views
Shortest unsatisfiable 3-CNF that can't be refuted with narrow resolution?
Proof width (the size of the largest clause in a proof) plays an important part in refuting an unsatisfiable formula. If a formula has a bounded-width resolution proof of its unsatisfiability, then ...
- 25
4
votes
1
answer
214
views
Finding a minimum cut with an upper bound on the set sizes
In the (unweighted) minimum k-cut problem, the goal is to partition the nodes in a given graph to at least $k$ subsets, such that the number of edges between different subsets is as small as possible.
...
- 5,720
0
votes
0
answers
32
views
Book recommendation: computability theory and Chomsky hierarchy
What is a good book for learning computability theory that covers the Chomsky hierarchy?
- 123
1
vote
1
answer
38
views
Does Sipser's _Introduction to the Theory of Computation_ cover the Chomsky hierarchy?
I saw the book suggested here.
Does Sipser's Introduction to the Theory of Computation cover the Chomsky hierarchy?
I ask since, looking through a pdf copy of the book, I found no matches with "...
- 123
0
votes
0
answers
22
views
Practical applications of finite model theory to databases
I have heard that finite model theory has connections to database theory. Is there an example of where this database theory could be used by programmers developing database applications?
- 287
0
votes
1
answer
123
views
Compiler optimization pass joining identical function definitions together (or specializing them)
Consider this program transformation, in any direction, written in ANF:
...
- 711
3
votes
0
answers
141
views
Maximum set cover with non-overlap
Let the universe be the set $U$ and a set of subsets $S$ be such that $\cup_{s \in S} s = U$. I am interested in computing the longest sequence of sets $s_1, ..., s_k$ such that:
$s_i \in S$ $\forall ...
- 31
1
vote
1
answer
19
views
Reference request for book on design patterns with foreword by Christopher Alexander
I do recall having found a book on software design patterns with a foreword by Christopher Alexander. Now, as is well known Alexander is credited as the creator of the concept of design patterns and ...
- 13
0
votes
0
answers
26
views
Introduction to Calculus of Inductive Constructions
Which books/notes teach Calculus of Inductive Constructions (CIC) without using a specific programming languages like Coq or Lean? I would like a reference that also doesn’t assume (naive) set theory, ...
- 101
1
vote
0
answers
37
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
18
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
30
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)?
- 237
0
votes
0
answers
37
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
52
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,308
2
votes
0
answers
46
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
10
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
1
vote
1
answer
33
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
27
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
50
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
86
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
11
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
72
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,802
2
votes
1
answer
76
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
33
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
385
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
3
votes
1
answer
423
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 ...
- 327
0
votes
1
answer
83
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
70
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 ...
- 275
2
votes
1
answer
55
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 \{...
- 413