CIS Department Talk - Thursday, March 30
The Department of Computer & Information Science & The Society of Computer Science Present:
| Speaker: | Dr. Oscar H. Ibarra | |
| Topic: | Computational Complexity Issues in Membrane Computing |
| Date: | Thursday, March 30, 2006 at 2:30pm |
| Place: | John Mulcahy Hall 403, Rose Hill Campus |
Abstract:
Membrane computing (MC) is a recent branch of molecular computing that aims to develop models and paradigms that are motivated by cell biology. MC identifies an unconventional computing model, namely a P system, which abstracts from the way living cells process chemical compounds in their compartmental structure. Thus, regions defined by a membrane structure contain multisets of objects that evolve according to specified rules. The objects can be represented as symbols or strings of symbols. By using the rules in a nondeterministic (deterministic) maximally parallel manner, transitions between the system configurations can be obtained. A sequence of transitions is a computation of how the system is evolving. Various ways of controlling the transfer of objects from a region to another and applying the rules, as well as possibilities to dissolve, divide or create membranes have been studied. P systems have a great potential for implementing massively concurrent systems in an efficient way that would allow us to solve currently intractable problems once future bio-technology gives way to a practical bio-realization. We present recent results that answer some interesting and fundamental open questions in the field. These concern complexity issues such as universality versus nonuniversality, determinism versus nondeterminism, membrane and alphabet-size hierarchies, and various notions of parallelism.
Bio:
Oscar H. Ibarra received his B.S. degree in Electrical Engineering from the University of the Philippines and his M.S. and Ph.D. degrees, also in Electrical Engineering, from the University of California, Berkeley. He is a Professor and past Chair of the Department of Computer Science at the University of California, Santa Barbara. Previously, he was with the faculties of UC Berkeley (1967-1969) and the University of Minnesota (1969-1990). His research interests include the design and analysis of algorithms, theory of computation, computational complexity, parallel computing, and formal verification. Oscar was awarded a John Simon Guggenheim Memorial Foundation Fellowship in 1984. He is a Fellow of the Association for Computing Machinery (ACM), the Institute of Electrical and Electronics Engineers (IEEE), the American Association for the Advancement of Science (AAAS), and the Minnesota Supercomputer Institute. In 2001, he received the IEEE Computer Society’s Harry M. Goode Memorial Award. He was presented an “Award of Distinction” in computer science by the Computing Society of the Philippines during the 6th International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN 2002). He received the 2002 Philippine-American Academy of Science and Engineering Founder’s Lectureship Award in Engineering at the academy’s 21st Annual Meeting and Symposium in Solomons Island, Maryland. He was awarded an Invitation Fellowship for research by the Japan Society for the Promotion of Science (JSPS) and visited the Japan Advanced Institute of Science and Technology (JAIST) in fall 2002. On the occasion of his 60th birthday, a workshop, Computer Science: From Theory to Practice, was held in Singapore in August 2002. The University of the Philippines Alumni Association (UPAA) presented him a distinguished alumnus award as the 2004 Outstanding Professional in the field of Mathematics, Statistics, and Computer Science. He was awarded the first P Prize in Membrane Computing in 2003. He was recently elected a member of the European Academy of Sciences (EAS). He is listed in the Institute for Scientific Information (ISI) database of 230 Highly Cited Researchers in Computer Science. Oscar is the Editor-in-Chief of the International Journal of Foundations of Computer Science. He is an Editor of Theoretical Computer Science, the Journal of Parallel and Distributed Computing, and Grammars: A Journal of Mathematical Research on Formal and Natural Languages. He has also served on the editorial boards of the IEEE Transactions on Computers, the IEEE Transactions on Parallel and Distributed Systems, and the Journal of VLSI Signal Processing. He is on the advisory committee of the IEEE Technical Committee on Parallel Processing and is a member of the IFIP Working Group on Cellular Automata.
For more information or directions, contact:
Ms. Diane Roche (718) 817-4480 or roche@cis.fordham.edu
|
