Computer Science

Questions tagged [reference-request]

Ask Question

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

862 questions
Newest
Active
Bountied
Unanswered
Filter by
Sorted by
Tagged with
0
votes
0answers
85 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
72 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
40 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
20 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
18 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
48 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
54 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
20 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
38 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
33 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
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
51 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
28 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
81 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
57 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
166 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
81 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
263 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
291 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
88 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/...

1 2 3 4 5 … 18