We present several results concerning the computational power and complexity of Accepting Networks of Splicing Processors (ANSP). We show that every recursively enumerable language can be accepted by an ANSP of size 7 out of which 6 do not depend on the given language. Then we propose a method for constructing, given an NP-language, an ANSP of size 7 accepting that language in polynomial time. Unlike the previous case, all nodes of this ANSP depend on the given language.
Abstract:
In my talk I briefly introduce a powerful proof assistant Coq, one of the most widely used automated
theorem proving tools today.
I illustrate the uses of Coq by providing several methods allowing to incorporate general recursive
(e.g., potentially non-terminating) recursive functions inside the underlying theory of this proof assistant.