Titlebook: Machines, Computations, and Universality; 5th International Co Jérôme Durand-Lose,Maurice Margenstern Conference proceedings 2007 Springer-

范例

On the Power of Networks of Evolutionary Processorsoid) every recursively enumerable language can be generated by a network with one deletion and two insertion nodes. Networks with an arbitrary number of deletion and substitution nodes only produce finite languages, and for each finite language one deletion node or one substitution node is sufficien

保存

浸软

More on the Size of Higman-Haines Sets: Effective Constructionsat these sets . be effectively computed in general. Here the Higman-Haines sets are the languages of all scattered subwords of a given language and the sets of all words that contain some word of a given language as a scattered subword. Recently, the exact level of unsolvability of Higman-Haines set

neologism

社团

极力证明

FACET

More on the Size of Higman-Haines Sets: Effective Constructionsn-Haines sets for the lower classes of the Chomsky hierarchy, namely for the families of regular, linear context-free, and context-free languages, and prove upper and lower bounds on the size of these sets.

相符

Query Completeness of Skolem Machine Computationsomplete Geolog trees is defined, and this tree concept is used to show logical completeness for Skolem machines: If the query for a Geolog theory is a logical consequence of the axioms then the corresponding Skolem machine halts succesfully in a configuration that supports the query.

Aqueous-Humor

Enthralling

Universality, Reducibility, and Completenessare based on the construction of reduction of problems; all considered concepts of reduction, as well as deduction in logic are kinds of reduction of abstract properties. The Church-Turing Thesis, which states universality of the class of all Turing machines, is considered in a mathematical setting as a theorem proved under definite conditions.