Questions tagged [reference-request]

Questions requesting papers in the literature on specific, narrow issues.

Filter by
Sorted by
Tagged with
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 ...
Alex Shpilkin's user avatar
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 ...
pyridoxal_trigeminus's user avatar
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 ...
user6767509's user avatar
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.
Dynamite's user avatar
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 ...
user avatar
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 ...
Bob Aiden Scott's user avatar
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} \...
Johan Thiborg-Ericson's user avatar
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 ...
Craig Gidney's user avatar
  • 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 ...
programonkey's user avatar
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 ...
SmileyCraft's user avatar
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 ...
Max Muller's user avatar
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 ...
Russell Easterly's user avatar
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-...
Tim's user avatar
  • 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 ...
Mike Battaglia's user avatar
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 ...
Mike Battaglia's user avatar
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 ...
Ankit Gayen's user avatar
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 ...
Ankit Gayen's user avatar
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 ...
Alec Rhea's user avatar
  • 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 (...
paulotorrens's user avatar
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 ...
Soha's user avatar
  • 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. ...
Erel Segal-Halevi's user avatar
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?
Sam's user avatar
  • 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 "...
Sam's user avatar
  • 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?
Andrew's user avatar
  • 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: ...
paulotorrens's user avatar
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 ...
in_question's user avatar
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 ...
Juan Meleiro's user avatar
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, ...
rfloc's user avatar
  • 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 ...
Rodrigo de Azevedo's user avatar
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 ...
George Hodgkins's user avatar
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)?
Evan Aad's user avatar
  • 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. ...
Danila Nikolaychuk's user avatar
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 ...
Martin Berger's user avatar
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 $...
vvg's user avatar
  • 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 ...
geeko's user avatar
  • 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 ...
The Limit Does Not Exist's user avatar
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 ...
Agnishom Chattopadhyay's user avatar
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 ...
Markus's user avatar
  • 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$...
Nicola Gigante's user avatar
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 ...
Nicola Gigante's user avatar
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 ...
Craig Gidney's user avatar
  • 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 ...
CutOnBumInBand's user avatar
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 ...
Joa's user avatar
  • 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 ...
Qualearn's user avatar
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 ...
Andrew Baker's user avatar
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 ...
M.N.Raia's user avatar
  • 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 ...
Somnium's user avatar
  • 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$, ...
H A Helfgott's user avatar
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$. ...
Lluís Alemany-Puig's user avatar
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 \{...
user6767509's user avatar

1
2 3 4 5
21