Questions tagged [reference-request]
Questions requesting papers in the literature on specific, narrow issues.
831
questions
2
votes
1answer
23 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
65 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
19 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
16 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
41 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
147 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
56 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
31 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
27 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
43 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
238 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
59 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
74 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
27 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
51 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
106 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
39 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
25 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 ...
2
votes
2answers
58 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
43 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
18 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
35 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
57 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
44 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
43 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
30 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 ...
6
votes
1answer
68 views
Type system with subtyping on abstract data types?
Consider this example on binary trees in some ML-like language:
...
2
votes
1answer
132 views
Dependent type system with different computation model
There exist various Turing-equivalent models of computation, such as lambda calculus, Turing machines, or register machines.
It seems that dependent type systems (like Coq, Agda, Idris, homotopy type ...
1
vote
0answers
31 views
Best-known Boolean Circuits for Clique? [closed]
Not having received a satisfactory response to this question in math.SE, I am asking it here:
In this question, it is mentioned that the best known Boolean circuits for the Clique problem are non-...
1
vote
0answers
16 views
State of the art of parser handling of offset errors
Say you are parsing a complicated binary file but there is 1 extra byte inserted somewhere. This could completely mess up the entire parse, but if you just looked ahead one token you would see the ...
1
vote
1answer
32 views
Randomized communication complexity of indexing
The function $\mathrm{INDEX}:\{0,1\}^n\times\{1,\dots,n\}\to \{0,1\}$ is defined as
$$\mathrm{INDEX}(x,i)=x_i,$$
where $x=x_1\dots x_n$. I am looking for the randomized communication complexity of $\...
5
votes
0answers
84 views
What is the state of the algorithmic art for floating point arithmetic on complex numbers?
Most modern compilers and processors implement the IEEE 754 binary formats for floating point numbers. IEEE 754 guarantees that the addition, subtraction, multiplication, division, and square root ...
1
vote
0answers
26 views
The underlying type theory of HOL/Isabelle
Is there a good source on the type theory of HOL/Isabelle/other HOL-based LCF-style theorem provers?
1
vote
1answer
35 views
additive hash function
Do functions with the following properties exists for x being arbitrary stream of bytes:
op(f(x1), f(x2))=f(x1+x2) and op(f(x1), f(x2))!=f(x2+x1) given that x1!=x2 where plus denotes concatenation ...
2
votes
0answers
23 views
Good examples of consistent/admissible heuristics in non-graphical domains?
I'm preparing lectures for intro to AI, and would like to give non-boring examples of heuristic functions.
Does anyone know examples of non-trivial consistent/admissible heuristics in non-geographic ...
5
votes
1answer
103 views
The definition of weakest precondition for a non-deterministic language
In the classical IMP language, the definition of weakest precondition is:
definition "wp c Q s ≡ ∃t. (c,s) ⇒ t ∧ Q t"
This is stating that from state s, after ...
0
votes
1answer
107 views
Boolean Functions Implemented by Multiplexers
Electrical engineers often use multiplexers to implement Boolean functions. What is the correct technical term for this model of computation? Is it Decision Tree model or is there another name?
1
vote
0answers
25 views
Summary of types of equivalence and equality in type theory, with notations and examples
Coming from non-computer science background, I am trying to understand the different types of equivalence and equality usually used in type theory. Ideally, I am looking for clear definitions and ...
1
vote
1answer
41 views
AVL Rotations Abbreviations
I read that there are 4 types of rotations:
Left rotation
Right rotation
Left-Right rotation
Right-Left rotation
What are the corresponding abbreviations: RL,LR,RR,LL? Is there a reference how to ...
0
votes
1answer
44 views
More efficient maximum bipartite matching
I've been looking into weighted matching in bipartite graphs and am currently looking at maximum matchings in weighted bipartite graphs. As I've been reading and poking around at different books and ...
-1
votes
1answer
95 views
Applications of divide-and-conquer outside of merge sort and quicksort [closed]
What are other algorithms that use the divide-and-conquer paradigm aside from merge sort and quicksort?
0
votes
0answers
12 views
How to denote a graph class which allows only $k$ instances of a certain induced subgraph?
Suppose that a graph class $\mathcal{C}$ is defined as follows:
A graph $G$ belongs to $\mathcal{C}$ if, and only if $G$ is chordal,
but has at most $k$ $5$-cycles.
I am aware that the ...
2
votes
1answer
128 views
What is the right term/theory for prediction of Binary Variables based upon their continuous value?
I am working with a linear programming problem in which we have around 3500 binary variables.
Usually IBM's Cplex takes around 72 hours to get an objective with a gap of around 15-20% with best ...
3
votes
1answer
468 views
In SAT, do we require an assignment for arbitrary variables?
I am reading about the Satisfiability Problem, in page (5) the author gives the following example :
$(P \lor Q \lor R) \wedge
(\bar{P} \lor Q \lor \bar{R}) \wedge
(P \lor \bar{Q} \lor S) \wedge
(\bar{...
