Theoretical Computer Science Stack Exchange
Theoretical Computer Science Stack Exchange

Most Popular

more tags
1500 questions
17
votes
3 answers

Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time?

Twenty years ago, I built an regular expression package that included conversions from regular expressions to a finite state machine (DFA) and supported a host of closed regular expression operations (Kleene star, concatenation, reverse, set…
Wesner Moise
  • 311
  • 2
  • 8
17
votes
2 answers

What is the origin of logical relations?

I actually have two questions: Who first used logical relations to relate semantics? I traced them back to Reynold's "On the Relation Between Direct and Continuation Semantics", but I can't claim to have made an exhaustive search. I have found…
Ohad Kammar
  • 2,677
  • 23
  • 28
17
votes
6 answers

Which is the limit of lossless compression data? (if there exists such a limit)

Lately I've been dealing with compression-related algorithms, and I was wondering which is the best compression ratio that can be achievable by lossless data compression. So far, the only source I could find on this topic was the…
Auron
  • 273
  • 1
  • 2
  • 6
17
votes
2 answers

Explicit mu-recursive expression for Ackerman function

Can you please point out how to build Ackerman function (actually I'm interested in a version proposed by Rózsa Péter and Raphael Robinson) via standard mu-recursive operators? I tried original papers by Péter and Robinson, but Péter's paper use a…
Artem Pelenitsyn
  • 1,103
  • 6
  • 20
17
votes
3 answers

Edit distance between two partitions

I have two partitions of $[1 \ldots n]$ and am looking for the edit distance between them. By this, I want to find the minimal number of single transitions of a node into a different group that are necessary to go from partition A to partition…
zenna
  • 835
  • 6
  • 11
17
votes
2 answers

H-free cut problem

Suppose you are given a connected, simple, undirected graph H. The H-free cut problem is defined as follows: Given a simple, undirected graph G, is there a cut (partition of vertices into two non-empty sets, L,R) such that graphs induced by…
Aryabhata
  • 1,855
  • 3
  • 21
  • 29
17
votes
1 answer

Approximation for counting the number of simple $s$-$t$ paths in a general graph

I have been told that there are some good polynomial time algorithms for approximating the number of simple paths in an directed graph from given starting vertex $s$ to given ending vertex $t$. Does anyone know of a good reference on this…
bbejot
  • 1,099
  • 6
  • 14
17
votes
1 answer

What is the name of this type of directed graph problem?

Take a directed graph $G$ where the edges are decorated with a a natural number. We want the set of all paths $P$ between two vertices $v_1$ and $v_2$ such that each successive edge in the path is decorated with a natural number that is greater…
Rob
  • 815
  • 8
  • 19
17
votes
0 answers

Sequences with sublogarithmic concat and approximate split

Is there a data structure for representing sequences that supports the operations: concat takes two sequences of size $m$ and $n$ and produces a new sequence of size $m+n$ by joining them in time $o(\lg \min(n,m/n))$ (or $o(\lg \min(m,n/m))$ if…
jbapple
  • 11,184
  • 2
  • 29
  • 50
17
votes
2 answers

Trace Equivalence vs LTL Equivalence

I am looking for an easy example of two transition systems that are LTL equivalent, but not trace equivalent. I have read the proof of Trace Equivalence being finer than LTL Equivalence in the book "Principles of Model Checking" (Baier/Katoen) but…
magnattic
  • 173
  • 7
17
votes
5 answers

Ambiguity and Logic

In automata theory (finite automata, pushdown automata, ...) and in complexity, there is a notion of "ambiguity". An automaton is ambiguous if there is a word $w$ with at least two distinct accepting runs. A machine is $k$-ambiguous if for every…
Arthur MILCHIOR
  • 1,561
  • 10
  • 19
17
votes
3 answers

Is there a name for "physical things out of which one can build a Turing machine"?

One of the amazing things about computer science is that the physical implementation is in some sense "irrelevant". People have successfully built computers out of several different substrates -- relays, vacuum tubes, discrete transistors,…
David Cary
  • 532
  • 3
  • 11
17
votes
2 answers

Is there a simple argument that shows that the unique games conjecture implies the PCP theorem

how can one show that what is relation between "Unique games conjecture" and "PCP theorem"? how does one explain "Unique games conjecture" is stronger form of "PCP theorem"?
j.s.
  • 705
  • 4
  • 11
17
votes
2 answers

Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?

The Constraint Satisfaction Problem I mentioned is similar to CNF-SAT: A variable can take values from some finite domain $D$ where $|D| = d$. A literal of variable $x$ is an expression of the form $x\neq c$, where $c\in D$. A constraint is a…
Junqiang Peng
  • 173
  • 8
17
votes
2 answers

Parameterized complexity of graph intersection number

What if anything is known about the parameterized complexity of computing the intersection number of a graph (the smallest number of cliques needed to cover all its edges)? It has long been known to be NP-complete, and it's obviously FPT because it…
David Eppstein
  • 50,990
  • 3
  • 170
  • 278
1 2 3
…
99 100