University of Vienna
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
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
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
complexity. The expression complexity results have been generalized to a method for a wide
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
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
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])
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.
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])
 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.
 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.
 J. Dorn. Iterative Improvement
Methods for Knowledge-based Scheduling, AI Communications, Vol. 8, no. 1. 1995, pp. 22-34.
 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
 T. Eiter. Generating Boolean I-Expressions.
Acta Informatica, 32:171-187, 1995.
 T. Eiter and G. Gottlob. The
Complexity of Logic-Based Abduction. Journal of the ACM, 42(1):3-42, January 1995.
 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.
 T. Eiter and G. Gottlob.
Identifying the Minimal Transversals of a Hypergraph and Related Problems. SIAM J. Comp.,
24(6):1278-1304, December 1995.
 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.
 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.
 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.
 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.
 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
 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.
 G.Gottlob, N.Leone, H.Veith.
Second Order Logic and the Weak Exponential Hierarchies. Proceedings Mathematical
Foundations of Computer Science (MFCS) 1995.
 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.
 G. Gottlob. NP Trees and Carnap's
Modal Logic. Journal of the ACM, Vol.42, 2, pp.421-457.
 G. Gottlob. Translating Default
Logic into Standard Autoepistemic Logic. Journal of the ACM, Vol.42, 4.
 G. Gottlob. Collapsing Oracle-Tape
Hierarchies. Proc. of the 11th Annual IEEE Conference on Computational Complexity, IEEE
 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.
 N. Leone, L. Palopoli, M. Romeo. A
Language for Updating Logic Programs. Journal of Logic Programming, 23(1), April 1995, pp.
 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.
 W. Slany. Scheduling as a fuzzy
multiple criteria optimization problem. Fuzzy Sets and Systems, 78:197-222, March 1996.
 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.
 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.
 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.
 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.
 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.
 H. Veith. Succinct Representation,
Leaf Languages, and Projection Reductions .Proc. of the 11th Annual IEEE Conference on
ComputationalComplexity, pp.118-126, IEEE Press, 1996.
Prof. Dr. Georg Gottlob
Institut fur Informationssysteme
Technische Universitat Wien
1040 WIEN Austria
Tel: +43 1 58801 6120
Fax: +43 1 5055304