Theoretical computer science and natural language processing group

Active research programs

The activity on Structural Complexity concentrates on various probabilistic extensions of the complexity classes P and NP. The class IP (lnteractive Proof Systems) captures the proof complexity of a powerful prover convincing a probabilistic verifier. This investigation has recently led to amazing results about the intractability (NP-completeness) of various approximation problems. An important result that we have shown is the following: the graph isomorphism problem is not NP-complete, unless the polynomial hierarchy collapses. It must be noted that it has been an open question ever since 1972 (when NP-completeness was defined) whether the graph isomorphism problem is in the class P or whether it is NP-complete. Collaboration with K. Sharma and Yu Lin of CUNY, G. Georgakopoulos of University of Crete.

Projects:

PSC-CUNY Research Award Program 1990-91.

Esprit-Project ALCOMP through the University of Patras.

Another thrust of the group's research has been the analysis, design and implementation of sequential and parallel algorithms for efficient solving of various graph problems (e.g. shortest routing) on planar graphs or other graphs used as models for street maps. The practical applications of these investigations have to do with routing and navigating vehicles in (city) traffic. For this purpose various decompositions of planar graphs into simple graphs have been studied.

Collaboration with: G. Pantziou, Ch. Zaroliaggis, P. Spyrakis, E. Kirousis, D. Kavadias of University of Patras and Y. Manousakis of University of Paris Sud.

Projects:

Esprit-Project ALCOMP through the University of Patras.

Node for the Human Capital and Mobility proposal "Graph Algorithms".

PENED 91ED145, "Design Techniques of Sequential and Parallel Algorithms for Planar Graphs, and Applications to Routing and Navigation Problems of Road Transportation Networks" (submitted).

A third area of interest has been Foundation of Logic and Functional Programming. For the case of logic programming we studied the approach of linear constraints. The language 2LP (linear programming and logic programming) has been employed. Another line of investigation led through the use of linear logic. Finally lambda-calculus has been used for the foundation of functional programming languages.

Collaboration with G. Koletsos, G. Stavrinos of the Math. Department of NTUA.

Projects:

PENED 91ED144, "Application of Logic Techniques in Logic Programming Languages " (approved) .

ESPRIT BRA 3230 working group: Common Foundations of Functional and Logic Programming.

For a better understanding of the foundation of distributed computing we study logic of knowledge as a special case of modal logics. We investigate communication patterns between agents, the time complexity of achieving agreement or even common knowledge. Various applications are planned .

Collaboration with R. Parikh, M. Fitting, and K. Georgatos of CUNY. Modern Greek Language specificities are recorded in a standard way. Morphological, syntactic and semantic linguistic information can be supplied to our software systems under various computational linguistic formalisms. Software tools already developed include a finite state automaton for Modern Greek morphology, a compiler-parser for unification grammar formalisms and a software system for Modern Greek word-class determination. User friendly systems developed include a Lexical DB as a computer aided instruction tool for Greek grammar learning and a Greek Word Processor in a PC-DOS environment. A current research project refers to the ISO 2022 virtual terminal implementation, where all European scripts (8-bit character sets) could easily be designated and invoked. Collaboration with the Linguistics Dpt. of the Athens University Prof. D. Theofanopoulou-Kontou) and the ELOT, Greece's Standardization Body (Mr. V. Melagrakis).