Questions tagged [reference-request]
Questions requesting papers in the literature on specific, narrow issues.
847
questions
2
votes
0answers
23 views
Simulating extensible sums with dependent types?
ML-style languages have a concept of "extensible" or "open" sum types, where variants can be declared at any point, and there's not a fixed number of constructors for the type. They're usually used to ...
3
votes
0answers
42 views
Number of maximal cliques in a graph where the largest induced cycle is $C_4$
So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices.
In general, it is exponential.
I am trying to determine whether the number ...
0
votes
0answers
6 views
Looking for good book similar Stability/Conditioning in Numerical Linear Algebra,
I am currently reading Numerical Linear Algebra by Trefethen and Bau and I am finding it quite difficult to read. In particular, I have been trying to read the sections on Floating Point Arithmetic, ...
1
vote
0answers
24 views
Randomized version of the class $APX$?
Is there a class which is to APX what BPP is to P?
I'm looking for a definition that is like the following:
"For $r > 0$, an $r$-RPCA (randomized polynomial-time constant-factor approximation) ...
4
votes
2answers
65 views
Defining $a^n b^{n^2}$ with one existential SO binary relation
Is it possible to define the language:
$$L = \{ a^n \; b^{n^2} \}$$
using an existential second order sentence over strings (ordered structures with unary predicates $U_a(x), U_b(x)$) using only ...
1
vote
0answers
33 views
How Expensive is Projecting onto a Polytope?
I have a problem where our action set is a polytope $\mathcal P\subset \mathbb R^d$ and an algorithm that involves projecting onto the action set. For example it says to select the Euclidean ...
0
votes
0answers
33 views
Good resource for graph theory
Frankly speaking I have many problem with symbols in graph such as (s:s') or v\S or some symbols such as those that I mentioned . Can anyone suggest a good resource or a good tutorial on the net that ...
0
votes
1answer
25 views
Knapsack up to the heaviest item
There are $n$ items with weights $w_1,\ldots,w_n$ and values $v_1,\ldots,v_n$. There is a knapsack with capacity $W$. A subset of items is called feasible up to heaviest item if, once the heaviest ...
0
votes
0answers
19 views
Looking for a pdf (or .ps.gz) of “Dualities of Domains”, 1993 thesis, Han Zhang
I'd like a (preferably free) copy (.pdf or, more likely .ps.gz given its 1993 date), of Han Zhang's thesis, Dualities of Domains, https://dl.acm.org/citation.cfm?id=920144
Easy enough to google it, ...
2
votes
0answers
18 views
Why are VFSMs not more commonly used?
For a job several years ago I worked with a team using technologies built around Virtual Finite State Machine models for system fault analysis and remediation. Since then, I've found it to be a ...
3
votes
3answers
61 views
Guidance for Theory of Computation
I have been studying Introduction to Theory of Computation by Micheal Sipser and I just complected it. Now I want to take this a step further what should I do next to increase my skills. I tried ...
0
votes
0answers
27 views
Who invented the adder, full-adder, half-adder?
I didn't find, in the digital design books, who invented the adders.
The same person invented the half-adder and the full-adder?
What's the oldest publication on digital arithmetic design?
1
vote
1answer
22 views
Maximum-cardinality matching in unbalanced bipartite graphs
Let $G = (X+Y, E)$ be a bipartite graph, and suppose we want to find a maximum-cardinality matching in $G$.
The Hopcroft-Karp algorithm runs in time $O(|E|\sqrt{|V|})$, where here $|V| = |X|+|Y|$. So ...
1
vote
1answer
53 views
Keeping track of best algorithms
Is there a site that keeps track of the "current best algorithms", e.g., for certain combinatorial optimization problems?
In the latter there exists a range of classic problems such as MIN st-CUT or ...
1
vote
1answer
20 views
What is known about the sets enumerated by primitive recursive functions?
Let's say that a set of natural numbers $S \subseteq \mathbb{N}$ is primitive recursively enumerable if there exists some primitive recursive function $f$ such that $S$ is the range of $f$. That is, ...
0
votes
0answers
32 views
A condition for $\emptyset \neq S\subset RE$ under which $L_S \notin RE$
I read some computation theory lecture notes and after citing and proving the proposition: $\emptyset \in S \Rightarrow L_S = \{\langle M \rangle : L(M)\in S\} \notin RE$ it says that $\emptyset\in S$ ...
6
votes
1answer
50 views
What publication first introduced the concept of a non-deterministic Turing machine?
What publication first introduced the concept of a non-deterministic Turing machine?
Turing did not define the concept in his 1936 paper.
1
vote
1answer
66 views
Where were the ideas of vote, accept and commit phases originally introduced?
In the Stellar Consensus Protocol SCP, the voting procedure follows a 3 phase commit i.e. vote, accept and confirm i.e. see section 5.
Is this a novel introduction or has this been previously been ...
2
votes
1answer
25 views
Algorithm to compute partitions of a graph in N cliques
does anyone know of an efficient algorithm to compute the partition of a graph in N cliques?
Notice that N is the number of the cliques and not the size of them.
I have heard of the 2 cliques ...
4
votes
1answer
79 views
Term for a graph decomposition based on a maximum matching
Let $M$ be a maximum cardinality matching in a bipartite graph $G(X+Y,E)$. Let $X_0$ be the subset of $X$ unmatched by $M$. Define the following sequence:
$Y_1 = $ the neighbors of $X_0$ using edges ...
1
vote
1answer
22 views
Any book for learning to correctly find out complexity of one's algorithm?
Suppose we have designed an Algorithm and we want to find out its complexity. I am looking for a book which mainly focuses on finding out complexity of algorithms rather than introducing me to ...
0
votes
1answer
33 views
String matching and bioinformatics [closed]
I'm interestd in string-matching, I would like to know recent open problems in string-matching in field of bioinformatics.
1
vote
0answers
21 views
Good Reference For Design And implementation Of Proof-Assistant
Hello I'm searching for any good review article or book about the design an implementation of a proof-assistant, something such as the Dragon book for programming language. My background is ...
2
votes
1answer
23 views
Parallelization of priority queue-based algorithms
There's a number of algorithms that operate by maintaining and consuming a priority queue of "events". I'm thinking primarily of geometric algorithms, particularly sweep-line algorithms like Bentley-...
0
votes
0answers
8 views
Reference request for finding minimum cost connected dominating set
I know that finding a connected dominating set has a $O(logn)$ factor,
I'm seeking a reference that achieves this ratio by giving an LP and rounding it (preferably randomized rounding).
1
vote
1answer
53 views
Examples for Partial Combinatory Algebras
I am currently working on my Bachelor thesis about Turing Categories (see Introduction to Turing Categories [1]). In this context I got some questions regarding Partial Combinatory Algebras (PCAs), ...
5
votes
2answers
159 views
List of major Open Problems in Computational Complexity and their Likelihood?
I remember reading an article/paper (or perhaps a talk, most probably by Scott Arranson) where he lists the major open problems and their likelihood of being true or false in a table/graph. This is ...
2
votes
1answer
68 views
The Ising Model and Computational Complexity
I've been told recently that one can use the Ising model can find solutions to certain NP-hard problems, such as Clique, although it doesn't do so in polynomial time.
Googling gets a few Arxiv ...
1
vote
1answer
33 views
In which reference can I find a definition for the equivalence of DFAs?
How is the equivalence of DFA defined? I found the equivalence of states --- James Hein, section 5.3, page 301. But he doesn't define equivalence between entire automata. (Ullman and Hopcropft seem ...
3
votes
1answer
30 views
Proof emptiness for PDA is $\mathcal{O}(n^3)$
It is well known that the emptiness problem vor PDAs is in $\mathcal{O}(n^3)$. I couldn't find a good paper proving this theorem. Furthermore a proof for VPAs would be fine for me as well if that is ...
3
votes
0answers
46 views
Conditions that imply closure under intersection of context-free languages
Context-free languages are not closed under intersection.
Suppose $L_1, L_2 \in CF \setminus REG$ (i.e., $L_1,L_2$ are context-free but not regular).
Are there well-known theorems (and/or whole ...
5
votes
1answer
248 views
How to prove the emptiness of intersection of two context free languages is undecidable?
Where can I find a proof that the emptiness problem for the intersection of two context free languages is undecidable? I searched on the internet but could not find anything helpful.
Do you maybe ...
3
votes
1answer
213 views
Reductions between LIS and LCS
Given an oracle that returns both the length and the subsequence for the Longest Increasing Subsequence of a given input $A$ of $n$ elements $\text{LIS}(A,n)$, can one use a polynomial number of calls ...
1
vote
1answer
85 views
Which time series prediction techniques are useful given harmonic properties?
I have a time series dataset where events have harmonic properties, and seemingly the nature of the event's early segments can determine the remainder of the event (see example 1's oscillations). ...
1
vote
0answers
65 views
Law as a computer science problem?
For a long time, computer scientists and logicians have noticed that law (statutes, contracts, adjudication, etc), has some similarity with formal logic and programming languages, and have approached ...
0
votes
0answers
28 views
Law and contracts as “programs” executed by human brains
Note: This question is NOT about using computers/AI in legal practice.
I found a paper (pdf here) that makes the analogy between law and computer programming:
Laws and contracts are programs/...
3
votes
0answers
76 views
Interesting applications of union-find
I've been trying to find interesting applications of union-find that are lesser known. Here are some popular algorithms based on union-find that I know:
Kruskal's algorithm for MST
Tarjan's off-line ...
1
vote
0answers
175 views
Inserting a new face in a Half Edge data structure (open-mesh and not)
I'm trying to figure how to implement face insertion in a halfedge data structure to represent 3D meshes, I think it's safe to assume I'll only deal with meshes that have disc topology.
Although I've ...
0
votes
0answers
28 views
Any good source explaining multiprocessor synchronization techniques and their implementation
I need to study how synchronization is done in a multiprocessor operating system, but I am unable to find a good source. I have read about it in the book "Modern Operating System" by Tanenbaum, but I ...
1
vote
1answer
40 views
Simple property of DFAs
Do you know if this simple property of a DFA is stated as a property (or theorem) in some Automata theory book (possibly with a particular name)?
Property: Given a DFA $A = \{ Q, \Sigma, \delta, q_0, ...
2
votes
1answer
31 views
Isomorphism problem on bounded degree digraphs
By Babai & Luks (1983), it was proved that graph isomorphism problem is tractable on bounded degree graphs. However, I could not find any result when the graph is edge directed.
Is isomorphism ...
3
votes
2answers
91 views
Size of tree decomposition
Given a graph $G$ with $n$ vertices, let $(X, T)$ be a tree decomposition of $G$ with the smallest width. Is the number of nodes in $T$ upper bounded by $n$? I have googled it but all materials I ...
1
vote
0answers
65 views
Lower bound on online range minimum query with element value modification
Is there a known lower bound to the online Range Minimum Query (RMQ) problem with value modifications (given the array we perform online RMQ on, support dynamically modifying the values of a given ...
2
votes
0answers
30 views
Definition of “data-directed programming”
Section 2.4.3 of SICP provides an example of data-directed programing in the context of dispatching on type, but I didn't find a general definition of what it is. Wikipedia article says that it is a ...
2
votes
0answers
39 views
Reference Request - Typed First-Order-Logic Book
There are many great references for computer scientists interested in untyped first order logic, such as Melvin Fitting's "First-Order Logic and Automated Theorem Proving" or John Harrison's "Handbook ...
1
vote
0answers
86 views
Confusion about the geometric interpretation of the simplex method for linear programming
In Section 7.6.2 of the textbook "Algorithms" by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, the authors provide a geometric interpretation of the two main tasks of each iteration of ...
0
votes
0answers
16 views
What year exactly did Dijkstra distribute EWD682?
The Dijkstra's archive says EWD682 was written or distributed between 1976--1979. I wonder if you can tell the exact year. It might not be easy since the archive itself didn't make it.
5
votes
1answer
47 views
“Functional dependencies” with cardinality constraints
Let us write $\{ A_1, \ldots, A_k\} \rightrightarrows^n \{B_1, \ldots, B_m\}$ for a relation $R$ if for all $\langle a_1, \ldots, a_k\rangle$ we have $\left\lvert \pi_{B_1, \ldots, B_m} \sigma_{\...
1
vote
1answer
54 views
If there is any sense of an optimal set of instructions in an ISA
So there are One Instruction Set Computers, having only one (complicated) instruction like addleq, "add and branch if less than or equal to zero". And then there ...
0
votes
0answers
32 views
Precisely when and where was Feynman's Computer Heuristics lecture given?
Feynman's Computer Heuristics lecture was apparently given at the Esalen Institute, Big Sur, California, in 1985. But I have no formal evidence of this. Has anyone ever cited this lecture that you ...
