Wyniki wyszukiwania - Biblioteka Nauki

1

$-Calculus of Bounded Rational Agents : Flexible Optimization as Search under Bounded Resources in Interactive Systems

100%

Eberbach E.

Fundamenta Informaticae

|

2005

|

tom Vol. 68, nr 1/2

47--102

EN

This paper presents a novel model for resource bounded computation based on process algebras. Such model is called the $-calculus (cost calculus). Resource bounded computation attempts to find the best answer possible given operational constraints. The $-calculus provides a uniform representation for optimization in the presence of limited resources. It uses cost-optimization to find the best quality solutions while using a minimal amount of resources. A unique aspect of the approach is to propose a resource bounded process algebra as a generic problem solving paradigm targeting interactive AI applications. The goal of the $-calculus is to propose a computational model with built-in performance measure as its central element. This measure allows not only the expression of solutions, but also provides the means to incrementally construct solutions for computationally hard, real-life problems. This is a dramatic contrast with other models like Turing machines, l-calculus, or conventional process algebras. This highly expressive model must therefore be able to express approximate solutions. This paper describes the syntax and operational cost semantics of the calculus. A standard cost function has been defined for strongly and weakly congruent cost expressions. Example optimization problems are given which take into account the incomplete knowledge and the amount of resources used by an agent. The contributions of the paper are twofold: firstly, some necessary conditions for achieving global optimization by performing local optimization in time and/or space are found. That deals with incomplete information and complexity during problem solving. Secondly, developing an algebra which expresses current practices, e.g., neural nets, cellular automata, dynamic programming, evolutionary computation, or mobile robotics as limiting cases, provides a tool for exploring the theoretical underpinnings of these methods. As the result, hybrid methods can be naturally expressed and developed using the algebra.

2

On Hypercomputation, Universal and Diagonalization Complete Problems

100%

Eberbach E.

Fundamenta Informaticae

|

2015

|

tom Vol. 139, nr 4

329--346

EN

In the paper we define the class of hypercomputation complete and hard undecidable problems. We prove that typical unsolvable problems are decidable in infinity. We hypothesize that all undecidable problems can be reduced in infinity to each other, i.e., they are H-complete (hypercomputation complete). We propose also two other classes: U-complete (universal complete) and D-complete (diagonalization complete) that use asymptotic reduction and allow separate non- RE and RE non-recursive undecidable classes.

3

Capturing evolution of polymorphic viruses

100%

Eberbach E.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2006

|

tom z. 156

125-138

EN

In this paper three models of polymorphic viruses are presented. These models had to capture self-reproduction, evolution and damaging payload of polymorphic viruses. They have been derived using a formal model of Evolutionary Computation the Evolutionary Turing Machine, cellular space models, and the $-calculus process algebra for problem solving. Some preliminary results associated with these models are discussed.

4

Universality for Turing Machines, Inductive Turing Machines and Evolutionary Algorithms

63%

Burgin M. , Eberbach E.

Fundamenta Informaticae

|

2009

|

tom Vol. 91, nr 1

53-77

EN

The aim of this paper is the development of foundations for evolutionary computations. To achieve this goal, a mathematical model of evolutionary automata is introduced and studied. The main classes of evolutionary automata considered in this paper are evolutionary Turing machines and evolutionary inductive Turing machines. Various subclasses and modes of evolutionary computation are defined. Problems of existence of universal objects in these classes are explored. Relations between Turing machines, inductive Turing machines, evolutionary Turing machines, and evolutionary inductive Turing machines are investigated.

5

Generalized Mutual Exclusion with semaphores only

51%

Ordman E. T. , Eberbach E. , Anwar A.

Fundamenta Informaticae

|

1999

|

tom Vol. 40, Nr 4

407-422

EN

The paper deals with a generic solution of the Mutual Exclusion Problem using semaphores only. We use in the solution weakly fair binary semaphores and (not necessarily fair) semaphores with initial value k. All semaphores are simple in that the P and V operations on them are paired in the natural way avoiding split semaphores. No auxiliary shared variables are used. We define a general form of the mutual exclusion problem. We claim: (1) All mutual exclusion problems can be solved using only simple semaphores. (2) All mutual exclusion problems can be solved fairly (with bounded waiting) using simple semaphores (weakly fair binary and initially-k semaphores). We give some bounds on how many semaphores are needed for standard problems. The solutions given may be inefficient: a mutual exclusion problem which can be solved in linear time and space with shared variables may require exponentially many semaphores.