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

learn more… | top users | synonyms

0
votes
0answers
6 views

Combining Production Rules using Reinforcement Learning

Production systems have been used to solve puzzles such as the Tower of Hanoi for years with hard-coded production rules. However, has there been any research in using reinforcement learning to ...
1
vote
0answers
18 views

Inherent complexity of testing line segment intersections with aligned and oriented bounding boxes?

It is well known that in practice, a substantial difference in run-time between algorithms for testing intersection of a line segment with aligned or oriented bounding boxes (in computer graphics ...
2
votes
1answer
24 views

Understanding the fundamentals of building an in-Memory Distributed Graph

I am working on a project where I have to build an in-memory distributed graph capturing the relation between similar files(based on some similarity metric) stored in shared file system over multiple ...
-1
votes
1answer
19 views

Books for studying C programming [on hold]

I'm studying in math department and have pretty good skills in math, but I have never had experiences with programming. I was going to self-study C programming, and my friend advised me the book of ...
0
votes
0answers
9 views

Reference notes for learning Matlab [on hold]

Im a complete beginner in computing and i am trying to learn some computing skills. I learning how to use Matlab as my first programming course. Are there are websites that have notes for matlab or ...
-1
votes
2answers
35 views

Parallel Algorithms for matrix multiplication

Are there any parallel algorithms designed for fast matrix multiplication? If so, can someone suggest me some online sources to read about them or could possibly brief it out here in their answer.
1
vote
1answer
23 views

Have block edit distances been computed on large code bases?

There is an enormous mass of source code in this world, and I think it's safe to say that most of this source code was once copied from elsewhere, then modified. There is a decent chance of the ...
3
votes
0answers
31 views

References on memory subsystems

I took a typical computer architecture class a long time ago as an undergrad and since then I've done a fair amount of low-level systems programming down to the assembly level and worked on OS ...
3
votes
1answer
35 views

Multi object image segmentation methods

I want to survey the state-of-the-art in image segmentation. Is there a paper on how to segment multiple objects in an image? The segmentation papers I read, normally identify one of the many objects ...
2
votes
1answer
38 views

Have non-regular language classes of infinite words been studied?

For regular languages we have $\omega$-regular languages which extend them to infinite words. Are there such extensions for CFG's, CSG's and recursively enumerable languages?
0
votes
0answers
46 views

Most frequently auto-tagging algorithms for text documents

Please if it's possible introduce the newest and most frequently auto-tagging algorithms for auto-tag text document. I want to get one text document and export tag for that. I also saw TF-IDF but it ...
-1
votes
2answers
49 views

Book reference: Programming Languages are for humans

Currently I'm writing my thesis and I made the assumption that all programming languages are made for humans and humans alone. There's no reason to make compromises to fit the machine needs. ...
4
votes
5answers
569 views

Is there any example of automatas (or similar) systems that emerge complex internal structures on its own?

Automatas are turing-complete grid-based systems with progression rules on which we can encode arbitrarily complex structures. For example, this is a "glider gun" on Conway's Game of Life: Due to ...
5
votes
2answers
106 views

Is there a research name for “systems that steadily grow in complexity as they are computed”?

I have an intuitive concept of systems that grows in complexity steadily as it computes. I can think in some examples: Nature. Given the physical laws, some initial conditions (say, the Earth planet ...
0
votes
0answers
11 views

Reference for Elliptical Basis Function Neural Networks

I found the following assertion in a neural networks FAQ: Radial networks typically have only one hidden layer, but it can be useful to include a linear layer for dimensionality reduction or ...
2
votes
1answer
21 views

Resource Request for a “Most Similar Vector Problem” on an Integer Lattice?

I am currently working on problem that I think could be expressed as an integer lattice problem, and hoping to find some guidance on this forum. Given $u \in \mathbb{R}^n$ and a bounded integer ...
-1
votes
0answers
22 views

zero-one goal programming algorithms - any new development?

I am trying to solve zero-one goal programming problem (media buying problem) and I am searching for the relevant algorithms but it seems to me that the development of algorithms (both for binary goal ...
4
votes
2answers
176 views

Good mathematical book on algorithms [closed]

I’m a sucker for mathematical elegance and rigour, and now am looking for such literature on algorithms and algorithm analysis. Now, it doesn’t matter much to me what algorithms are covered, but very ...
1
vote
0answers
47 views

Who first invented and analysed algorithm of finding median in a stream of integers using two heaps?

There is popular problem: Given that integers are read from a data stream, find the median of elements read so far in an efficient way. One of possible solutions: Use max-heap for left heap ...
1
vote
0answers
18 views

Prior papers on hash walks [closed]

Random walks are well known from probability theory. I have the idea for hash walks. If h(x) is a hash function and a,b,c,d,e,f is a boolean sequence then the sort of hash walk I am talking about is ...
3
votes
1answer
38 views

Formal languages: constructing * for a linear set

Right now, I'm working on a computer verified proof in Agda, showing that the Parikh images of regular languages are semi-linear (i.e. a limited form of Parikh's Theorem). Right now, I'm trying to ...
1
vote
2answers
34 views

Finding a minimum set of dependencies in a cycle-filled dependency graph

I have a graph of a large number of targets. Each target depends on a list of other targets. The graph is very large and filled with cycles of dependencies. My goal is to find the smallest subset of ...
1
vote
0answers
25 views

Algorithms for operating on tape storage [closed]

Old algorithm textbooks often covered algorithms that did well on tape drives, since tape drives used to be a common storage type on almost all computers. Since memory on modern CPUs with data ...
6
votes
2answers
134 views

Eliminate non-local references from closure

For a code similarity detection framework I need to eliminate references to non-local variables, for example having the following closure: ...
2
votes
1answer
74 views

Determine if items can be ordered grouping two simultaneous criteria

For a set of items with two properties, how can it be detemined if they can be ordered in a way so that for every value of either property all items of that value are grouped together. Obviously ...
0
votes
0answers
19 views

Are there any algorithms or researches on finding local alignments in partially ordered sequences?

The question is a bit unclear, so let me explain. Finding local alignments in sequences like protein sequence is a well studied area in bioinformatics, and I do not think there is any lack of ...
1
vote
0answers
30 views

How can neural networks learn to create new things (sentences for example)? [closed]

I have already taken a college course at my uni on machine learning where we implemented all the basic ML programs: linear regression, logistic regression, basic neural network with logistic ...
2
votes
2answers
26 views

Problem of finding pairs of elements that co-occur in some number of sets

I have a fairly general problem and I wonder if it has a name. The problem statement, as best I can put it, is the following: Let $I=\{i_1,i_2,...,i_n\}$ be a set of items. Let ...
1
vote
1answer
32 views

Data versioning in a relational database

I've been working on an industrial project where my job was to design a data model in-memory and in a relational database in such a way, that can capture the time-varying nature of the production ...
2
votes
1answer
104 views

Graph Families that are easy to color

What are the non-trivial graph families that have a known chromatic number, or an easy way (polynomial-time algorithm) to compute the latter. Examples would be: Kneser graphs Chordal graphs Do ...
3
votes
1answer
68 views

Data structure for ordered counted set

Is there a name for a counted set (multiset) that is ordered? For example lets say this data structure represents a shopping cart (or basket if you're British). The shopping cart shows the order the ...
7
votes
3answers
105 views

Algorithms for minimizing Moore automata

Brzozowski's algorithm can be extended to Moore automata but its time complexity is exponential in general. Is there any other algorithm for minimization of Moore automata? What are the running times ...
2
votes
0answers
21 views

Cobham's characterization of FP

Does anyone know of an accessible introduction to Cobham's model independent characterization of FP and it's equivalence to the standard definition using Turing machines? The best source I could find ...
3
votes
0answers
29 views

A syntactic property of computing systems: is non-coding DNA universal?

One of the surprising aspect of the genome for lay-people is that it contains important non-coding DNA parts, which does not mean that they are all useless. I never paid so much attention to the fact, ...
6
votes
3answers
161 views

When did polynomial-time algorithm become of interest?

I would like to understand why and when polynomial algorithms became of interest. When did people realize the role and importance of efficient versus non-efficient algorithms? Did that happen when ...
0
votes
1answer
84 views

Complete examples of program correctness proofs

Does anyone have any complete example of a proof of program correctness? I'm talking about something that includes the usual predicate, base case, inductive hypothesis, and inductive step. But also ...
3
votes
1answer
63 views

Travelling Salesman which can repeat cities

In the TSP problem, we usually assume a complete graph. If we can only visit each city once, we need a complete graph to ensure that there will be a path from every city to every other city. This is ...
2
votes
1answer
35 views

Algorithms that are using John's ellipsoid

The Lowner–John ellipsoid is a minimum volume enclosing ellipsoid of some convex body $K$. This ellipsoid is unique (as is the maximum volume ellipsoid contained in $K$). I'm looking for ...
3
votes
2answers
185 views

Implementing wait-free consensus with queues

Using Herlihy's model and definition of the wait-free hierarchy, a queue (a shared object with enqueue and dequeue) has consensus number 2, because we can initialize the queue with some value, and the ...
7
votes
1answer
57 views

Is there any published paper about automated planning software used in the ESA Rosetta mission?

The Rosetta spacecraft has reached a comet in August 2014 and sent a lander on its surface. It was one of the greatest science news of the year. Automated Planning and Scheduling techniques are ...
4
votes
1answer
53 views

Is it known whether the MD5 algorithm is surjective?

Does MD5 map to all possible 128 bit numbers? To put it another way: For every 128 bit number y, does there exist at least one x ...
1
vote
3answers
104 views

Is there a name for an inverted state machine?

I recently needed something like a state machine, but with a slightly different use case. In general, I would say a state machine knows about a set of states, and different events. Depending on the ...
2
votes
1answer
38 views

Dominator Tree for DAG

Is there a fast algorithm to compute dominator tree for acyclic graphs? The Lengauer-Tarjan Algorithm is a fast algorithm for general flowgraphs. But if a graph is acyclic, do we have a faster ...
1
vote
1answer
34 views

Ordered knapsack problem?

I'm trying to find the name of this problem, and with it a reasonable algorithmic solution. Setup: There are $n$ items with weights $w_1,\dots,w_n$, and $m<n$ buckets with target weights ...
1
vote
1answer
84 views

How important is it to find a deterministic polynomial time algorithm to construct Ramanujan graphs? [closed]

As in I don't know what is the difference between say the conferences SODA, STOC or FOCS. Measured in terms of such conferences, where would such a result be publishable? This is not a "technical" ...
4
votes
1answer
54 views

Who invented the state elimination algorithm for converting finite automata into regular expressions?

The state elimination algorithm is an algorithm for converting finite automata into regular expressions. It's found in many textbooks, including Sipser's Introduction to the Theory of Computation. ...
1
vote
0answers
35 views

sets of axioms for LADR automated theorem provers

I am pretty new to ATP, but I'm really enjoying playing around with prover9. I have found a nice set of axioms for basic information-theoretic proofs here, I was wondering if there are some ...
1
vote
0answers
28 views

NPDA, guessing capability and stack as an exclusive resource

Context Free languages is exactly the class of languages recognized by Nondeterministic Push Down Automata (NPDA). We can view a nondeterministic transition as a guess; for example if $L = \{x x^R ...
3
votes
0answers
24 views

Efficient algorithms for mutual, inverse, or round-trip Personalized PageRank

I'd like to implement a similarity between two nodes (X and Y) of a graph based on a simple extension of the Personalized PageRank algorithm, either: (Mutual PageRank): the product of the PPR of Y ...
8
votes
4answers
305 views

Why is binary search called binary search?

I heard several possible explanations, so I would like some trustable reference. Update 05.19: I'm interested in the question because one of mine students wrote in his thesis that the name comes from ...