Klaus Draeger
• Member for 10 years, 8 months
• Last seen this week

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 ...

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 ...

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 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 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 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 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 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 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 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\}, ...

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 ...

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 ...

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 ...

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 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 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 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 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 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 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\...

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 ...

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 ...

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 . ...

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 ...
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 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 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 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 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 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 ...