Questions tagged [reference-request]
Questions requesting papers in the literature on specific, narrow issues.
864
questions
-3
votes
0answers
39 views
What are some generalizations of the tree diameter?
I am specifically interested in extensions and generalizations of the diameter concept on graphs. I can't find anything relevant in google scholar.
I have a certain result about tree diameters that ...
0
votes
0answers
18 views
In what sense the computer program (Turing machine) can be considered as the complex system and its IIT Phi can be measured and improved?
I am reading https://global.oup.com/academic/product/a-world-beyond-physics-9780190871338?cc=us&lang=en& about one approach of complex systems' theory for the emergence of the life. It is ...
0
votes
0answers
88 views
A sort of job scheduling problem
I have been thinking about the following problem:
Let $J$ be a set of jobs that need to be performed. Each jobs comprises of some number ($>1$) of tasks, and a job is considered finished when all ...
0
votes
0answers
11 views
Synthesis of the crisp programs from the Bayesian (probabilistic) programs?
https://arxiv.org/abs/2001.00805 is the article which is pointing towards the direction that the optimal policy of the reinforcement learning can be expressed as the Bayesian/probabilistic program (...
1
vote
1answer
23 views
Upper bound on the average number of overlaps for an interval within a set of intervals
Let $\mathcal{I}$ be a set of intervals with cardinality $L$, where each interval $I_i \in \mathcal{I}$ is of the form $[a_i, b_i]$ and $a_i, b_i$ are pairwise distinct non-negative integers bounded ...
3
votes
1answer
73 views
What should I read to understand semantics of programming languages?
I would like to have a good conceptual understanding of the semantics of programming languages: operational-, denotational-, axiomatic-, categorical-.
Is there a good (standard?) textbook for this?
2
votes
1answer
41 views
Image segmentation of a high resolution 2D binary image into clusters, threads and points
I use python3 script to find out the area proportion of pixel clusters, threads and points in my image. They are originally 8-bit greyscale TIFF images with a resolution of 2048x2168 pixels. I have ...
0
votes
1answer
19 views
Textbook for understanding formal grammars
I am looking to understand the Chomsky Hierarchy. I've read some textbooks that touch on formal grammars (textbooks on computability, which relate automata to specific sets of formal grammars, notably ...
0
votes
1answer
21 views
Clarifying what it means to be Strongly NP-Complete
Wikipedia defines strongly NP-Complete as:
A problem is said to be strongly NP-complete, if it remains so even when all of its numerical parameters are bounded by a polynomial in the length of the ...
0
votes
0answers
19 views
Textbook for Hoare logic
I am looking to understand what Hoare logic is, and how it is used to prove program-correctness. I am interested in an applied text, which shows how to actually state formal specifications of programs,...
2
votes
0answers
32 views
Estimating number of points in 1D space
There are some arbitrary-chosen points in 1D space. What needs to be found is the approximate number of them without counting all of them. It is possible to choose some coordinates (numbers) and for ...
2
votes
2answers
52 views
What goes into proving two complicated programs are equivalent?
Say I wanted to prove that two programs were equivalent (either rigorously if possible, or informally if not). More specifically, say I have something relatively complex such as an HTTP server ...
0
votes
0answers
15 views
Simulating Boolean Circuit with RAM
Statement:
Every $T(n)$ size bounded Boolean circuit family, could be simulated with $(T(n))^2$ time bounded Random Access Turing Machine (RAM).
Could you please supply me with a reference to an ...
1
vote
0answers
11 views
When was the dynamic array first introduced as an example for amortized analysis?
I'm writing a report on amortized analysis, and I'm using the example of a dynamic array to explain each method. I think it would be nice to add a reference to when this example was first used, as it ...
3
votes
0answers
46 views
Have Rackoff's coverability bounds been improved?
In "The covering and boundedness problems for vector addition systems", Rackoff considers a vector addition system $(v,A)$ of dimension $k$ and size $n$ and derives an upper bound of $2^{2^{(\log_2 3)...
1
vote
1answer
55 views
Is SEMIPRIME in P?
The title says it all: is there a deterministic polynomial time algorithm that tests for semiprimality? (A number $N$ is a semiprime if it is the product of two primes.) I don't understand the ''...
2
votes
0answers
41 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
47 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
7 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
66 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
34 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
30 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
20 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
21 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
66 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
42 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
34 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
55 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
21 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
33 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
53 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
75 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
29 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
82 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
24 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
35 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
23 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
24 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
58 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), ...
6
votes
2answers
169 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
83 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
34 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
39 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
47 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
268 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
298 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
89 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). ...
