Search results for "COMPLETENESS"
showing 6 items of 66 documents
K4-free Graphs as a Free Algebra
2017
International audience; Graphs of treewidth at most two are the ones excluding the clique with four vertices (K4) as a minor, or equivalently, the graphs whose biconnected components are series-parallel. We turn those graphs into a finitely presented free algebra, answering positively a question by Courcelle and Engelfriet, in the case of treewidth two. First we propose a syntax for denoting these graphs: in addition to parallel composition and series composition, it suffices to consider the neutral elements of those operations and a unary transpose operation. Then we give a finite equational presentation and we prove it complete: two terms from the syntax are congruent if and only if they …
Lambda substitution algebras
1993
In the paper an algebraic metatheory of type-free λ-calculus is developed. Our version is based on lambda substitution algebras (λSAs), which are just SAs introduced by Feldman (for algebraizing equational logic) enriched with a countable family of unary operations of λ-abstraction and a binary operation of application. Two representation theorems, syntactical and semantic, are proved, what directly provides completeness theorems.
Performability of Actions
2021
AbstractAction theory may be regarded as a theoretical foundation of AI, because it provides in a logically coherent way the principles of performing actions by agents. But, more importantly, action theory offers a formal ontology mainly based on set-theoretic constructs. This ontology isolates various types of actions as structured entities: atomic, sequential, compound, ordered, situational actions etc., and it is a solid and non-removable foundation of any rational activity. The paper is mainly concerned with a bunch of issues centered around the notion of performability of actions. It seems that the problem of performability of actions, though of basic importance for purely practical ap…
Ultrametric Finite Automata and Turing Machines
2013
We introduce a notion of ultrametric automata and Turing machines using p-adic numbers to describe random branching of the process of computation. These automata have properties similar to the properties of probabilistic automata but complexity of probabilistic automata and complexity of ultrametric automata can differ very much.
Edelstein-Suzuki-type resuls for self-mappings in various abstract spaces with application to functional equations
2016
Abstract The fixed point theory provides a sound basis for studying many problems in pure and applied sciences. In this paper, we use the notions of sequential compactness and completeness to prove Eldeisten-Suzuki-type fixed point results for self-mappings in various abstract spaces. We apply our results to get a bounded solution of a functional equation arising in dynamic programming.
How Do Cancer Registries in Europe Estimate Completeness of Registration?
2008
Summary Objectives: Several methods for estimating completeness in cancer registries have been proposed. Little is known about their relative merits. Before embarking on a systematic comparison of methods we wanted to know which indicators were currently in use and whether there had been comparative investigations of estimation methods. Methods: We performed a survey among European cancer registries asking which methods for estimating completeness they used and whether they had performed comparisons of methods. Results: One hundred and ninety-five European cancer registries were contacted after identification using membership directories of the European Network of Cancer Registries (ENCR) a…