Semi-supervised node classification in attributed graphs, i.e., graphs with node features, involves learning to classify unlabeled nodes given a partially labeled graph. Label predictions are made by jointly modeling ...
详细信息
We present a recursive formulation of the Horn algorithm for deciding the satisfiability of propositional clauses. The usual presentations in imperative pseudo-code are informal and not suitable for simple proofs of i...
详细信息
P systems are computing conceptual computing devices that are at least as powerful as Turing machines. However, until recently it was not known how one can encode any recursive function as a P system. Here we propose ...
详细信息
Function contracts are a well-established way of formally specifying the intended behavior of a function. However, they usually only describe what should happen during a single call. Relational properties, on the othe...
详细信息
It is well known that many theorems in recursion theory can be "relativized". This means that they remain true if partial recursive functions are replaced by functions that are partial recursive relative to ...
详细信息
What can be decided or semidecided about a primitive recursive function, given a definition of that function by primitive recursion? What about subrecursive classes other than primitive recursive functions? We provide...
详细信息
We describe a line of work that started in 2011 towards enriching Isabelle/HOL's language with coinductive datatypes, which allow infinite values, and with a more expressive notion of inductive datatype than previ...
详细信息
ISBN:
(纸本)9783319661674;9783319661667
We describe a line of work that started in 2011 towards enriching Isabelle/HOL's language with coinductive datatypes, which allow infinite values, and with a more expressive notion of inductive datatype than previously supported by any system based on higher-order logic. These (co)datatypes are complemented by definitional principles for (co)recursive functions and reasoning principles for (co)induction. In contrast with other systems offering codatatypes, no additional axioms or logic extensions are necessary with our approach.
MapReduce environments offer great scalability by restricting the programming model to only map and reduce operators. This abstraction simplifies many difficult problems occuring in generic distributed computations li...
详细信息
ISBN:
(纸本)9783319642031;9783319642024
MapReduce environments offer great scalability by restricting the programming model to only map and reduce operators. This abstraction simplifies many difficult problems occuring in generic distributed computations like fault tolerance and synchronization, hiding them from the programmer There are, however, algorithms that cannot be easily or efficiently expressed in MapReduce, such as recursive functions. In this paper we extend the Apache Spark runtime so that it can support recursive queries. We also introduce a new parallel and more lightweight scheduling mechanism, ideal for scheduling a very large set of tiny tasks. We implemented the aformentioned scheduler and found that it simplifies the code for recursive computation and can perform up to 2.1x faster than the default Spark scheduler.
Godel's System T is the simply typed lambda calculus extended with numbers and an iterator. The higher-order nature of the language gives it enormous expressive power-the language can represent all the primitive r...
详细信息
ISBN:
(数字)9783662553862
ISBN:
(纸本)9783662553862;9783662553855
Godel's System T is the simply typed lambda calculus extended with numbers and an iterator. The higher-order nature of the language gives it enormous expressive power-the language can represent all the primitive recursive functions and beyond, for instance Ackermann's function. In this paper we use System T as a minimalistic functional language. We give an interpretation using a data-flow model that incorporates ideas from the geometry of interaction and game semantics. The contribution is a reversible model of higher-order computation which can also serve as a novel compilation technique.
We introduce the concept of one-time nondeterminism as a new kind of limited nondeterminism for finite state machines and push-down automata. Roughly speaking, one-time nondeterminism means that at the outset the auto...
详细信息
ISBN:
(纸本)9783319602523;9783319602516
We introduce the concept of one-time nondeterminism as a new kind of limited nondeterminism for finite state machines and push-down automata. Roughly speaking, one-time nondeterminism means that at the outset the automaton is nondeterministic, but whenever it performs a guess, this guess is fixed for the rest of the computation. We characterize the computational power of one-time nondeterministic finite automata (OTNFAs) and one-time nondeterministic pushdown devices. Moreover, we study the descriptional complexity of these machines. For instance, we show that for an n-state OTNFA with a sole nondeterministic state, that is nondeterministic for only one input symbol, (n + 1)(n) states are sufficient and necessary in the worst case for an equivalent deterministic finite automaton. In case of pushdown automata, the conversion of a nondeterministic to a one-time nondeterministic as well as the conversion of a one-time nondeterministic to a deterministic one turn out to be non-recursive, that is, the trade-offs in size cannot be bounded by any recursive function.
暂无评论