Questions tagged [reference-request]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
99 views

Fastest way to find a substring 'ab' inside a string 'abab'

Let $A$ be an input alphabet - a finite set of symbols. Elements of $A$ are called the characters. The alphabet I am interested in is the set of all ordinary letters ...
1
vote
2answers
99 views

resource on translating imperative programs to functional programs

I'm not asking this question for the purpose of any particular project. Rather, I'm trying to understand how to translate non-trivial programs in imperative style to functional style. By functional ...
1
vote
0answers
20 views

Self reduction for fully introspective lambda calculus representations

For some representation scheme $\ulcorner \cdot \urcorner$, a self interpreter $R$ is a lambda expression where $R \ulcorner A \urcorner \underset{\beta}{=} A$, while a self reducer $E$ is a lambda ...
7
votes
1answer
97 views

Good book on the history of programming languages?

I'd like to read a book on the history of programming languages, that places their development into the context of their times. What was the context in which concepts like structured programming, ...
0
votes
0answers
27 views

Textbook on how processors are actually structured at the circuit level

I am looking for a textbook that helps me understand how basic digital electronic units are used to build complicated integrated circuits. I have looked online for textbooks, but what I have found ...
1
vote
0answers
40 views

Diameter of a random graph

I'm considering the standard Erdös/Renyi $G(n,p)$ model where we have $n$ nodes and each possible edge is sampled independently with probability $p = \frac{1}{n^\epsilon}$. It is relatively ...
2
votes
1answer
54 views

Finding C-convex holes in a planar point set

I am looking for an efficient algorithm to find convex holes in a given point set. The problem is Given $n$ points in the Euclidan plane, and a constant $c$, determine how many empty convex ...
1
vote
1answer
60 views

trace vs. computation vs. run vs. execution vs. walk

Many folks use the terms "trace", "execution", "computation", "run", "walk" ... interchangeably when they speak about state machines with labeled transitions. Does any work distinguish between these ...
6
votes
0answers
127 views

Time complexity of linear programming with small number of variables

I have a linear program with $n$ variables, $m$ constraints and $O(nm)$ bit total length (the constraint matrix contains only zeros and ones). I am interested in finding a polynomial time algorithm ...
0
votes
0answers
30 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
115 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 ...
1
vote
1answer
40 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 ...
4
votes
1answer
123 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
246 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
75 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
37 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 ...
3
votes
0answers
34 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
381 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 ...
2
votes
0answers
26 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
20 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 ...
2
votes
1answer
279 views

How to translate automatons (Turing machines) into programs of high level programming language?

Every program in high level ("industrial") programming language can be expressed as some Turing machine. I guess, that there exists universal algorithm for doing that (e.g. one can take the ...
1
vote
1answer
90 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
66 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 ...
7
votes
1answer
219 views

Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph [closed]

So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices. In general case, it is exponential. I am trying to determine whether the ...
1
vote
0answers
32 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
73 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
45 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
36 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
124 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 ...
2
votes
0answers
28 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 ...
2
votes
3answers
327 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
1answer
252 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
121 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
57 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
29 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
37 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
57 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
96 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
33 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
99 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
27 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
41 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
29 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 ...
3
votes
1answer
33 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-...
1
vote
1answer
97 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
219 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
210 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
40 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
162 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
52 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 ...

1 2
3
4 5
20