# Tagged Questions

**0**

votes

**0**answers

31 views

### two model-checking problems on nondeterministic finite automata: are they in $\mathsf{P}$?

Let us consider a slight modification of a nondeterministic finite automaton, let us name it a "weighted nondeterministic finite automaton" $\mathcal{A}$ which is a tuple $(Q, \Sigma, \Delta, q_0, ...

**2**

votes

**1**answer

103 views

### QBF of exponential length?

We consider a slightly extended version of a nondeterministic finite automaton, call it a "propositional nondeterministic finite automaton". It is defined as follows. Consider a fixed propositional ...

**1**

vote

**0**answers

92 views

### Schönhage's SMM with only one instruction

It is possible to implement $\lambda$-calculus in SchÃ¶nhage's storage modification machine using an infinite set of nodes and one single program consisted exclusively of (about hundred) instructions ...