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 pi-calculus, 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 Omega-optimization), 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 non-recursive 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 evolvable-cost-driven hardware, DNA-based 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 cost-driven computers. The NSERC and ONR supported projects on $-calculus have been aiming at investigation, design and implementation of a wide class of adaptive real-time distributed complex systems exhibiting meta-computation 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 object-oriented, 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