
News
Seminar, Department of Computer Science
The $Calculus Process Algebra for Problem Solving: A Paradigmatic Shift in Handling Hard Computational Problems
Eugene Eberbach
Professor at Department of Engineering and Science
Rensselaer Polytechnic Institute, Hartford
Wednesday, October 10, 2007
Abstract:
The $calculus is the extension of the picalculus, built around the
central notion of cost and allowing infinity in its operators. The
unique feature of the $calculus is its support for problem solving by
incrementally searching for solutions and using cost to direct its
search. We propose the $calculus as a more complete model for
problem solving to provide a support to handle intractability and
undecidability. It goes beyond the Turing Machine model. We define
the semantics of the $calculus using a novel optimization method
(called the k Omegaoptimization), which approximates a nonexisting
universal search algorithm and allows the simulation of many other
search methods. In particular, the notion of total optimality has
been utilized to provide an automatic way to deal with intractability
of problem solving by optimizing together the quality of solutions and
search costs. The sufficient conditions needed for completeness,
optimality and total optimality of problem solving search are
defined. A very flexible classification scheme of problem solving
methods into easy, hard and solvable in the limit classes has been
proposed. In particular, the third class deals with nonrecursive
solutions of undecidable problems. The approach is illustrated by
solutions of some intractable and undecidable problems. We also
briefly overview two possible implementations of the $calculus.
The $calculus provides a very general model for problem solving. In
particular, it is applicable to robotics, software agents, neural
nets, and evolutionary computation. The $calculus can be used for
design of cost languages (SEMAL, GBML, CCL), cellular
evolvablecostdriven hardware, DNAbased computing and bioinformatics
(including sequence alignment and protein folding), electronic
commerce, modeling reactive sensor networks, polymorphic viruses and
quantum computing. The $calculus leads to a new programming paradigm
cost languages, and a new class of computer architectures costdriven
computers. The NSERC and ONR supported projects on $calculus have
been aiming at investigation, design and implementation of a wide
class of adaptive realtime distributed complex systems exhibiting
metacomputation and optimization. The $calculus has has been applied
to the Office of Naval Research CCL (Common Control Language) for
Autonomous Underwater Vehicles (AUVs) at NUWC, Newport, RI, and SAMON
robotics testbed at Applied Research Lab, Penn State University. Some
preliminary ideas have also been utilized in the 5th Generation ESPRIT
SPAN project on integration of objectoriented, logic, procedural and
functional styles of programming in parallel architectures.
Bio: Dr. Eberbach is a Clinical Associate Professor at
Department of Engineering and Science, Rensselaer Polytechnic
Institute, Hartford, USA. Previously he was an Associate Professor at
Computer and Information Science Department and Intercampus Graduate
School of Marine Sciences and Technology, University of Massachusetts
Dartmouth, USA; a Professor with tenure at School of Computer Science,
Acadia University and an Adjunct Professor at Faculty of Graduate
Studies, Dalhousie University, Canada; Senior Scientist at Applied
Research Lab, The Pennsylvania State University; Visiting Professor at
The University of Memphis, USA; Research Scientist at University
College London, U.K.; Assistant Professor in Poland, and he also has
industrial experience. Professor Eberbach's current work is in the
areas of process algebras, resource bounded optimization, autonomous
agents and mobile robotics. General topics of interest are new
computing paradigms, languages and architectures, distributed
computing, concurrency and interaction, evolutionary computing and
neural nets. Dr. Eberbach is the author of more than 140 publications
in the above areas and he has been a recipient of 17 external research
grants. More information about projects, publications, courses taught
can be found at http://www.ewp.rpi.edu/~eberbe
Hosted by: Boleslaw K. Szymanski (x2714)
Last updated: June 8, 2007

