Technical University of Vienna

Nicola Leone

The Information Systems Departement of the Technical University of Vienna includes fourteen researchers: Jurgen Dorn, Thomas Eiter, Mario Girsch, Georg Gottlob, Thomas Hawelka, Marcus Herzog, Nicola Leone, Cristinel Mateis, Gerald Pfeifer, Wolfgang Slany, Katrin Seyr, Markus Stumptner, Helmut Veith and Franz Wotawa.

The department hosts the CD-Laboratory for Expert Systems funded by the Austrian Industries Corp. The aim of this laboratory is to do basic research in the field of expert systems while keeping close contacts to various affiliates of the Austrian Industries Corp.

The research group of the Information Systems Departement is active in several areas related to logics and databases. In particular, the main areas of research include Knowledge Representation and Reasoning, Algorithms in Computational Logic, Finite Model Theory, Fuzzy Reasoning, Constraint Processing, Implementation of Deductive Systems, Model-Based Reasoning.

Knowledge Representation and Reasoning

In this area we have defined formalisms for the representation of various forms of human reasoning and investigated their use as advanced query languages for data and knowledge bases. In particular, we have proposed several extensions of logic programming with true negation, disjunction, inheritance, and other object-oriented abstraction mechanisms. Moreover, we have defined new models for abduction from logic programs and default theories. ([1,9,12,21,22])

Algorithms in Computational Logic

We have investigated the computational complexity of basic reasoning tasks in a large number of non monotonic formalisms and in logic programming, which serves as a basis for the future development of algorithms. Moreover, we have investigated the connection between the computational paradigm of trees over NPs with modal logic, and we have developed algorithms for the manipulation of Boolean formulas and related problems. ([5,6,7,8,17])

Finite Model Theory

Using Finite Model Theory as link between database theory, logic, and complexity theory, we have investigated disjunctive datalog from the point of view of logical expressiveness and expression complexity. The expression complexity results have been generalized to a method for a wide range of logics and query languages, with the theory of succinct problems as the main tool used. Moreover, we have investigated generalized (Lindstrom) and second order quantifiers over finite models: We have obtained complexity characterizations and normal forms for such logics, and have established relationships to oracle computation and NP optimization problems. ([13,11,15,16,29])

Implementation of Deductive Systems

We have defined efficient techniques and algorithms for the computation of advanced logic programming semantics and exploited them for the actual implementation of deductive systems. In particular, we have studied the implementation of the leading semantics for negation and disjunction paying particular care to the detection and to the efficient computation of tractable subclasses of programs. ([1,20,21])

Fuzzy Reasoning

Research covers theory, systems and applications of fuzzy logic based constraints in combination with constraint satisfaction problem techniques to solve hard combinatorial optimization problems approximately, also including diagnosis and consistency checking of fuzzy constraint knowledge bases. ([23,24,25])

Constraint Processing

For knowledge-based scheduling applications we have formulated a model of soft constraints. These are used on one side to evaluate schedules and on the other side the concept of a greatest constraint violation is used by iterative improvement methods (tabu search, simulated annealing, iterative deepening, and genetic algorithms) as a heuristic to fasten the improvement cycle. ([2,3,4])

Model-Based Reasoning

The goal of model-based reasoning is the establishment of formal (usually logic) models describing the knowledge about a particular domain, and then deriving a desired set of solutions from this knowledge. In recent years research in this area in the department dealt mainly with model-based diagnosis applied to the area of software debugging and the automatic configuration of technical systems. ([14,26,27,28])

References

[1] F. Buccafurri, N. Leone, P. Rullo. Stable Models and their Computation for Logic Programming with Inheritance and True Negation. Journal of Logic Programming, 27(1), April 1996, pp. 5-43.

[2] J. Dorn, W. Slany. A flow-shop with compatibility constraints in a steelmaking plant. in Intelligent Scheduling, eds. Monte Zweben and Mark Fox, Morgan Kaufmann, 1994.

[3] J. Dorn. Iterative Improvement Methods for Knowledge-based Scheduling, AI Communications, Vol. 8, no. 1. 1995, pp. 22-34.

[4] J. Dorn, R. Kerr, G. Thalhammer. Reactive scheduling: improving the robustness of schedules and restricting the effects of shop floor disturbances by fuzzy reasoning International Journal on Human-Computer Studies, Vol. 42, 1995, pp. 687-704

[5] T. Eiter. Generating Boolean I-Expressions. Acta Informatica, 32:171-187, 1995.

[6] T. Eiter and G. Gottlob. The Complexity of Logic-Based Abduction. Journal of the ACM, 42(1):3-42, January 1995.

[7] T. Eiter and G. Gottlob. On the Computational Cost of Disjunctive Logic Programming: Propositional Case. Annals of Mathematics and Artificial Intelligence, 15(3/4):289-323, 1995.

[8] T. Eiter and G. Gottlob. Identifying the Minimal Transversals of a Hypergraph and Related Problems. SIAM J. Comp., 24(6):1278-1304, December 1995.

[9] T. Eiter, G. Gottlob, N. Leone. Semantics and Complexity of Abduction from Default Theories. Proc. of the 14th International Joint Conference on Artificial Intelligence - IJCAI 95', August 20-25, 1995, pp.870-876. To appear on Artificial Intelligence.

[10] T. Eiter and G. Gottlob. On the Expressiveness of Frame Satisfiability and Fragments of Second Order Logic. Technical Report CD-TR 96/92, Christian Doppler Laboratory for Exp ert Systems, TU Vienna, Austria, Februrary 1996. Accepted for publication in Journal of Symbolic Logic.

[11] T. Eiter, G. Gottlob, and Y. Gurevich. Normal Forms for Second-Order Logic over Finite Structures, and Classification of NP Optimization Problems. Annals of Pure and Applied Logic, 78:111-125, 1996.

[12] T. Eiter, G. Gottlob, N. Leone. Complexity Results for Abductive Logic Programming. Proc. of the 3rd Logic Programming and Non-Monotonic Reasoning Conference - LPNMR 95, Lexington, KY, USA 26-28 June 1995, pp. 1-14. To appear on Theoretical Computer Science.

[13] T. Eiter, G. Gottlob, and H. Mannila. Adding Disjunction to Datalog. In Proceedings of the Thirteenth ACM SIGACT SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-94), pages 267-278, Ma y 1994.

[14] G. Friedrich, M. Stumptner, F. Wotawa. Model-Based Diagnosis of Hardware Designs. In Proceedings on the European Conference on Artificial Intelligence-ECAI'96, Budapest, August 1996.

[15] G.Gottlob, N.Leone, H.Veith. Second Order Logic and the Weak Exponential Hierarchies. Proceedings Mathematical Foundations of Computer Science (MFCS) 1995.

[16] G. Gottlob. Relativized Logspace and Generalized Quantifiers over Finite Structures. Proc. Tenth Annual Symposium on Logic in Computer Science LICS'95 (San Diego, CA, June 1995), IEEE Press. To appear in Journal of Symbolic Logic.

[17] G. Gottlob. NP Trees and Carnap's Modal Logic. Journal of the ACM, Vol.42, 2, pp.421-457.

[18] G. Gottlob. Translating Default Logic into Standard Autoepistemic Logic. Journal of the ACM, Vol.42, 4.

[19] G. Gottlob. Collapsing Oracle-Tape Hierarchies. Proc. of the 11th Annual IEEE Conference on Computational Complexity, IEEE Press, 1996.

[20] N. Leone, P. Rullo. BQM: A System Integrating Logic, Objects and Non-Monotonic Reasoning. Proc. of the 7th IEEE International Conference on Tools with Artificial Intelligence-ICTAI'95, Washington, November 5-8, 1995. To appear on IEEE-TKDE.

[21] N. Leone, L. Palopoli, M. Romeo. A Language for Updating Logic Programs. Journal of Logic Programming, 23(1), April 1995, pp. 1-61.

[22] N. Leone, P. Rullo, F. Scarcello. Declarative and Fixpoint Characterizations of Disjunctive Stable Models Proc. of International Logic Programming Symposium-ILPS'95, December 4-7, 1995.

[23] W. Slany. Scheduling as a fuzzy multiple criteria optimization problem. Fuzzy Sets and Systems, 78:197-222, March 1996.

[24] W. Slany. CheckFLIP++: A knowledge acquisition tool for the fuzzy constraints-based *FLIP++ scheduling library. Proc. of Int. Conf. on Information Processing and Management of Uncertainty in Knowledge-Based Systems-IPMU'96, July 1996.

[25] W. Slany and J. Vavsvcak. A consistency checker for a fuzzy diagnosis system applied to warm rolling-mills in steelmaking plants. Proc. of IEEE Conf. on Fuzzy Systems, September 1996.

[26] M. Stumptner, A. Haselbock, and G. Friedrich. COCOS - a tool for constraint-based, dynamic configuration. In Proceedings of the 10th IEEE Conference on AI Applications (CAIA), San Antonio, March 1994.

[27] M. Stumptner, F. Wotawa. Model-Based Diagnosis of Hardware Description Languages. In Proceedings of Computational Engineering in Systems Applications CESA'96 IMACS Multiconference, Invited Session on Model-Based Systems, Lille, May 1996.

[28] M. Stumptner and F. Wotawa. A Model-Based Approach to Software Debugging. In Proceedings of the 7th International Workshop on Principles of Diagnosis, Val Morin, Canada, October 1996.

[29] H. Veith. Succinct Representation, Leaf Languages, and Projection Reductions .Proc. of the 11th Annual IEEE Conference on ComputationalComplexity, pp.118-126, IEEE Press, 1996.

Contact Person:

Prof. Dr. Georg Gottlob

Institut fur Informationssysteme

Technische Universitat Wien

Paniglgasse 16,

1040 WIEN Austria

Tel: +43 1 58801 6120

Fax: +43 1 5055304

Email: gottlob@dbai.tuwien.ac.at