0
votes
0answers
30 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
1answer
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
0answers
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 ...