Klaus Draeger
  • Member for 10 years, 8 months
  • Last seen this week
Why is non-determinism (Push-down automata) necessary?
Accepted answer
25 votes

I'm not quite sure which flavour of "why" you are looking for. One reason for the increase in power when allowing nondeterminism can be seen in the following example: Let $L$ be the set of ...

View answer
Explicit mu-recursive expression for Ackerman function
Accepted answer
14 votes

Breaking the Ackermann function all the way down to the elementary operators would really be quite lengthy, but here is a sketch: Note that when computing $A(m,x)$ recursively, at any point of the ...

View answer
Is the Set of all Primitive Words a Prime Language?
Accepted answer
13 votes

The answer is yes. Suppose we have a factorization $Q = A\cdot B$. One easy observation is that $A$ and $B$ must be disjoint (since for $w\in A\cap B$ we get $w^2\in Q$). In particular, only one of $...

View answer
Isomorphic graph embeddings in the Euclidean Space
Accepted answer
12 votes

This is not possible in general. The 4-cycle is actually helpful to consider: embedding it in $\mathbb{R}^k$ in the way you describe requires the images of all four vertices to be coplanar, forming a ...

View answer
Measurable language which is not $\omega$-regular
Accepted answer
11 votes

A simple class of examples can be found by considering singleton languages $\{w\}$. These are measurable (Let $C_n(w)$ be the set of words agreeing with $w$ up to the $n$-th letter, then $\{w\}$ is ...

View answer
Verifying a subtlety of Karp's original proof that SAT has a polynomial time reduction to 3SAT
9 votes

The conjunction of the first two clauses, $(\sigma_1\cup\sigma_2\cup u_1)(\sigma_3\cup\ldots\cup\sigma_m\cup\bar{u}_1)$ is equisatisfiable to the original clause, as can be easily checked (any ...

View answer
CTL and LTL logic difference
Accepted answer
9 votes

There are already some rather good related answers regarding LTL versus CTL. In a nutshell, LTL is first and foremost a logic of traces, and an LTL formula is true for a transition system $S$ if and ...

View answer
Directed multigraphs as minimal automata
Accepted answer
8 votes

Any absorbing node $n$ will have to be either accepting or not (so that either everything or nothing is accepted once $n$ is entered). If the graph has more than two absorbing nodes, then some of them ...

View answer
Constant in Komlos conjecture
8 votes

A simple way of obtaining a lower bound $c\ge\sqrt{2}$ is to consider pairs of vectors $u,v\in\mathbb{R}$. First of all, it makes sense to focus on pairs of unit vectors for which all $\{-1,1\}$-...

View answer
The number of states of local automata
Accepted answer
7 votes

Since you say that $T_w:=\{\delta(q,w):q\in Q\}$ should have at most one element, I'll assume that you use the version of DFA where $\delta$ can be partial. Then this is a counterexample: $X=\{a,b\}, ...

View answer
What kind of language is needed to recognize an ordered list? [multihead automata, apparently]
Accepted answer
7 votes

It sounds like what you are looking for are multihead automata (in your case, 1-way 2-head deterministic finite automata should suffice). I'm not really an expert on these, but google turns up some ...

View answer
Which kind of grammar is the following?
6 votes

The simple answer would be that, having an infinite set of rules, this is not a grammar in the usual sense. Languages over infinite alphabets have been investigated, but usually using register ...

View answer
Alternating automata
Accepted answer
6 votes

Expanding on Markus' answer a bit, note that the alphabet $\Sigma$ is in turn the powerset $2^{Prop}$ of the set $Prop=\{p_1,\dots,p_k\}$ of atomic propositions, i.e. it represents the set of ...

View answer
Complexity of digraph homomorphism to an oriented cycle
5 votes

For the intermediate question (a core with three top-bottom runs), how about this? Some notation: I will be describing runs by words in $\{l,r\}^*$, with e.g. $llrl$ corresponding to a subgraph $\...

View answer
A special case of the boolean multivariate quadratic polynomial problem
Accepted answer
5 votes

This case is still NP-hard. Suppose we have an instance of 3-SAT: $F=C_1\wedge\ldots\wedge C_n; C_i=L_{i,1}\vee L_{i,2}\vee L_{i,3}$, where each literal $L_{i,j}$ is either $V$ or $\neg V$ for some ...

View answer
Proof that the theory of rationals is convex
Accepted answer
4 votes

The key idea here is that for any conjunction of equations $F\equiv u_1=v_1\wedge\ldots\wedge u_k=v_k$, the set $S_F$ is convex in the geometric sense, i.e. for any two points $p,q\in S_F$, all points ...

View answer
Existence of certain graph gadget related to coloring odd hole free graph
Accepted answer
4 votes

One can extract an argument that this cannot work from the paper found by OP in the MO thread. Suppose $G=(V,E)$ is as required, and $c:V\to[k]$ is a $k$-coloring. By the assumption, $c(u)\neq c(v)$. ...

View answer
Decidability of membership in the fixed point of a rational relation
Accepted answer
4 votes

The answer to (1) is no, even for deterministic transducers. The reason is that we can encode configurations (tape contents + head position + machine state) of Turing machines into words such that the ...

View answer
What is a probabilistic function and where can I learn more about them?
Accepted answer
4 votes

The definition you give is essentially the one you need. A probabilistic function from $X$ to $Y$ assigns to each $x\in X$ a subdistribution of elements of $Y$ (rather than a single $y\in Y$). Such a ...

View answer
Relation between Kleene star, union and difference in relation algebra
Accepted answer
4 votes

Consider $S=\{1,2,3\}$ and relations $A=\{(1,3)\}, B=\{(1,2)\}, C=\{(2,3)\}$. Then $A^*=(A\setminus B)^*= A\cup\{(i,i)\ |\ i\in S\}$, $(B\cup C)^* = \{(i,j)\ |\ i,j\in S, i\le j\}$, and $C^* = C\...

View answer
Independent iterations in Las Vegas algorithms
Accepted answer
4 votes

Rapid restarts in SAT solving are one area where the sequence introduced in Luby,Sinclair,Zuckerman is used. See for example Section 2.1 in http://www.st.ewi.tudelft.nl/~marijn/publications/rapid.pdf ...

View answer
Minmax vs Maxmin
Accepted answer
3 votes

First of all, there is a lot of information in this related question: Max Min of function less than Min max of function. That said, the source of your problem is a confusion about which choices are ...

View answer
Simplest Machine Model Accepting $L = \{ww^Rw\;|\; w\in \Sigma^*\}$
3 votes

One answer here are multihead automata, see for example the survey Marek Chrobak: Hierarchies of one-way multihead automata, http://www.sciencedirect.com/science/article/pii/0304397586900939 . ...

View answer
How to constrain a finite automaton (NFA and DFA) to a tree?
Accepted answer
3 votes

I think the easiest way of enforcing tree shape is the set of conditions $q_0$ is not in the image of $\delta$, $\delta$ is injective, and $M$ is connected (to avoid isolated cycles). Note that this ...

View answer
Assignment of values for a set
3 votes

The problem as stated now is solvable in linear time. To see this, suppose $p\in P$ is such that there are $x\in X$ and $w\in W$ with $p_i=x_iw_i$ for all $i$. This means on the one hand that $1=\...

View answer
Kripke model and LTL vs CTL formulae interpretation
Accepted answer
3 votes

Intuitively, what happens here is that for $AFGp$, you check each individual path for whether after some point, $p$ will always be true - no matter what other choices are available in a given state. ...

View answer
Expressiveness of Büchi vs CTL(*)
Accepted answer
3 votes

One thing we have to be clear on is the kind of property we are talking about: CTL and CTL* are branching-time logics, used to talk about tree languages, whereas LTL is a linear-time logic, which per ...

View answer
How to XOR automata?
Accepted answer
2 votes

I guess the main reason why you could not find anything about this is that it is rarely needed (and can be reduced to the better-known boolean operations, as you noted). Checking language equivalence ...

View answer
Are there digraphs such that any two arborescences are arc-disjoint?
Accepted answer
1 votes

Leaving aside the trivial case (graphs which only have one $r$-arborescence), this won't be possible. Suppose $(V,E)$ is an $r$-arborescence of $(V,A)$. Then $E$ contains some (nonzero) number of ...

View answer
Is the value of $\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{n-f^Tf}$ polynomially computable?
1 votes

Without any further constraints, this expression will in general be unbounded, so the maximum won't exist. Let $V$ be $\{v_1,\ldots,v_n\}$ with $n\ge 2$. Pick $i\neq j$ such that $v_i,v_j$ are not ...

View answer