New answers tagged

0

Suppose we have a DPDA with $\epsilon$ transitions, $M$. Define a configuration of $M$ to be a pair $\langle p,s \rangle$ where $p$ is a state and $s$ is a stack; and define the silhouette of $\langle p,s \rangle$ to be the pair $(p,y)$ where $y=\textrm{top}(s)$ is the symbol at the top of the stack $s$. Define a subroutine called SimpleLoop as follows: ...


3

A decision tree is a model of computation which makes sense for instance of constant size. In contrast, a language is usually a collection of instances of unbounded size. An automaton (in this context) is a model of computation which describes a language. The upshot of all this is that in most circumstances, it doesn't really make sense to convert a decision ...


1

Let $L_1$ be the language of all $(M, p, y)$ such that if we start $M$ (a DPDA with $\epsilon$ transitions) in state $p$ with a stack consisting of only $y$ (which is either a single symbol or nothing), then reading an empty string as input would cause $M$ to eventually return to state $p$, with a $y$ on top of its stack if $y$ was a symbol rather than ...


1

The point of investigating a parametrized problem is that we hope or assume that the parameter will be fairly small or even bounded by a known small constant in some particular case you encounter in practice. In that case, algorithms with FPT could be called efficient. So yes, you can definitely pick an arbitrary parameter that will be very large in practice,...


Top 50 recent answers are included