Questions tagged [reference-request]

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

Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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$, ...
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 \{...
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 ...
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 ...
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 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 ...
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 ...
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. ...
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 $\{...
user avatar
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 ...
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 ...
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]$...

1
2 3 4 5
20