Skip to main content
SpringerLink
Log in

CoLab: A hybrid knowledge representation and compilation laboratory

  • Knowledge And Structures: How To Represent, Handle, And Find Knowledge And Insight Into Structure
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

Knowledge bases for real-world domains such as mechanical engineering require expressive and efficient representation and processing tools. We pursue a declarative-compilative approach to knowledge engineering.

While Horn logic (as implemented in PROLOG) is well-suited for representing relational clauses, other kinds of declarative knowledge call for hybrid extensions: functional dependencies and higher-order knowledge should be modeled directly. Forward (bottom-up) reasoning should be integrated with backward (top-down) reasoning. Constraint propagation should be used wherever possible instead of search-intensive resolution. Taxonomic knowledge should be classified into an intuitive subsumption hierarchy.

Our LISP-based tools provide directtranslators of these declarative representations into abstract machines such as an extended Warren Abstract Machine (WAM) and specialized inference engines that are interfaced to each other. More importantly, we provide source-to-sourcetransformers between various knowledge types, both for user convenience and machine efficiency.

These formalisms with their translators and transformers have been developed as part of CoLab, acompilationlaboratory for studying what we call, respectively, ‘vertical’ and ‘horizontal’ compilation of knowledge, as well as for exploring the synergeticcolaboration of the knowledge representation formalisms.

A case study in the realm of mechanical engineering has been an important driving force behind the development of CoLab. It will be used as the source of examples throughout the paper when discussing the enhanced formalisms, the hybrid representation architecture, and the compilers.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A. Abecker, TAXLOG: Taxonomische Wissensrepräsentation und Logische Programmierung, Projektarbeit (1993), in German.

  2. J.F. Allen, Maintaining knowledge about temporal intervals, Commun. ACM 26 (1983) 832–843.

    Google Scholar 

  3. F. Baader, H.-J. Bürckert, B. Hollunder, W. Nutt and J.H. Siekmann, Concept logics, Technical Report RR-90-10, DFKI, Kaiserslautern, Germany (1990).

    Google Scholar 

  4. F. Baader and P. Hanschke, A scheme for integrating concrete domains into concept languages, in:Proc. 12th Int. Joint Conf. on Artificial Intelligence (1991).

  5. F. Baader and P. Hanschke, Extensions of concept languages for a mechanical engineering application, inProc. German Workshop on Artificial Intelligence. GWAI-92 (Springer, September 1992).

  6. J. Backus. Can programming be liberated from the von Neumann style? A functional style and its algebra of programs. Commun. ACM 21 (1978) 613–641.

    Google Scholar 

  7. I. Balbin and K. Ramamohanarao, A generalization of the differential approach to recursive query evaluation, J. Logic Progr. 4 (1987) 259–262.

    Google Scholar 

  8. F. Bancilhon and R. Ramakrishnan, An amateur's introduction to recursive query processing strategies, inProc. ACM SIGMOD Conf. (ACM, 1986) pp. 16–52.

  9. F. Bancilhon and R. Ramakrishnan, Performance evaluation of data intensive logic programs, in:Foundations of Deductive Databases and Logic Programming, ed. J. Minker (Morgan Kaufmann, Los Altos, CA, 1988) pp. 441–517.

    Google Scholar 

  10. C. Beeri and R. Ramakrishnan, On the power of magic, J. Logic Progr. 10 (1991) 255–299.

    Google Scholar 

  11. H. Beringer and F. Porcher, A relevant scheme for Prolog extensions: CLP(conceptual theory), in:Proc. ICLP 89 (1989) 131–148.

    Google Scholar 

  12. H. Boley, A relational/functional language and its compilation into the WAM, SEKI Report SR-90-05, Universität Kaiserslautern, Fachbereich Informatik (April 1990).

  13. H. Boley, Extended logic-plus-functional programming, in:Workshop on Extensions of Logic Programming, ELP '91, Stockholm 1991, LNAI (Springer, 1992).

  14. H. Boley, A direct semantic characterization of RELFUN, in:Proc. 3rd Int. Workshop on ELP '92, eds. E. Lamma and P. Mello, vol. 660 of LNAI (Springer, 1993).

  15. H. Boley, K. Elsbernd, H.-G. Hein and T. Krause, RFM manual: Compiling RELFUN into the relational/functional machine, Document D-91-03, DFKI (1991).

  16. H. Boley, P. Hanschke, M. Harm, K. Hinkelmann, T. Labisch, M. Meyer, J. Mueller, T. Oltzen, M. Sintek, W. Stein and F. Steinle, μCAD2NC: A declarative lathe-workplanning model transforming CAD-like geometries into abstract NC programs, Technical Report Document D-91-15, University of Kaiserslautern, DFKI (November 1991).

  17. A. Borgida, R.J. Brachman, D.L. McGuinness and L.A. Resnick, CLASSIC: A structural data model for objects, in:Int. Conf. on Management of Data, ACM SIGMOD (1989).

  18. R.J. Brachman, V.P. Gilbert and H.J. Levesque, An essential hybrid reasoning system: knowledge and symbol level accounts in KRYPTON, in:Proc. 9th Int. Joint Conf. on Artificial Intelligence (August 1985) pp. 532–539.

  19. R.J. Brachman and J.G. Schmolze, An overview of the KL-ONE knowledge representation system, Cognitive Sci. 9 (1985) 171–216.

    Google Scholar 

  20. W.J. Clancey, Heuristic classification, Art. Int. 27 (1985) 289–350.

    Google Scholar 

  21. D. DeGroot and G. Lindstrom (eds.),Logic Programming: Functions, Relations, and Equations (Prentice-Hall, 1986).

  22. Y. Descotte and J.-C. Latombe, Making compromises among antagonist constraints in a planner, Art. Int. 27 (1985) 183–217.

    Google Scholar 

  23. F. Donini, B. Hollunder, M. Lenzerini, A.M. Spaccamela, D. Nardi and W. Nutt, The complexity of existential quantificatoin in concept languages, Research Report RR-91-02, DFKI (January 1991).

  24. C. Falter, Compilation von Vorwärtsregeln in einer hybriden Expertensystem-Shell, Diploma thesis, University of Kaiserslautern, FB Informatik (1992), in German.

  25. C.L. Forgy,OPS5 User's Manual, Carnegie-Mellon University, Department of Computer Science, Pittsburgh, PA 15213 (1981).

    Google Scholar 

  26. F. Frayman and S. Mittal, COSSACK: A constraints-based expert system for configuration tasks, in:Knowledge Based Expert Systems in Engineering: Planning and Design, eds. D. Sriram and R. Adey, Computational Mechanics (1987).

  27. E. Freuder, Synthesizing constraint expressions, Commun. ACM 21 (1978) 958–966.

    Google Scholar 

  28. L. Fribourg, SLOG: A logic programming language interpreter based on clausal superposition and rewriting, in:1985 Symposium on Logic Programming (IEEE Computer Society Press, 1985) pp. 172–184.

  29. M.R. Genesereth and R. Fikes, Knowledge interchange format version 3.0 reference manual, Technical Report Logic-92-1, Stanford University, Computer Science Department, Logic Group (June 1992).

  30. P. Hanschke, Specifying role interaction in concept languages, in:3rd Inter. Conf. on Principles of Knowledge Representation and Reasoning (KR '92) (October 1992).

  31. P. Hanschke and K. Hinkelmann, Combining terminological and rule-based reasoning for abstraction processes, in:Proc. German Workshop on Artificial Intelligence, GWAI-92 (Springer, September 1992).

  32. H.-G. Hein and M. Meyer, A WAM compilation scheme, in:Logic Programming: Proc. of the 1st and 2nd Russian Conf., ed. A. Voronkov, volume 592 of LNAI (Springer, 1992) pp. 201–214.

  33. R. Helm and K. Marriott, Declarative graphics, in:3rd Int. Conf. on Logic Programming (ICLP), ed. E. Shapiro, LNCS 225 (Springer, July 1986) pp. 513–527.

  34. K. Hinkelmann, Bidirectional reasoning of horn clause programs: Transformation and compilation, Technical Memo TM-91-02, DFKI (January 1991).

  35. K. Hinkelmann, Forward logic evaluation: Developing a compiler from a partially evaluated meta interpreter, Technical Memo TM-91-13, DFKI (October 1991).

  36. K. Hinkelmann, Forward logic evaluation: Compiling a partially evaluated meta-interpreter into the WAM, in:Proc. German Workshop on Artificial Intelligence, GWAI-92 (Springer, September 1992).

  37. B. Hollunder, W. Nutt and M. Schmidt-Schauß, Subsumption algorithms for concept description languages, in:9th European Conf. on Artificial Intelligence (ECAI'90) (Pitman Publishing, 1990) pp. 348–353.

  38. C. Klauck, R. Legleitner and A. Bernardi, FEAT-REP: Representing features in CAD/CAM, in:4th Int. Symp. on Artificial Intelligence: Applications in Informatics, Cancun, Mexico (1991). An extended version is also available as Research Report RR-91-20, DFKI.

  39. A. Kobsa, The SB-ONE knowledge representation workbench, in:Preprints of the Workshop on Formal Aspects of Semantic Networks, Two Harbors, CA (1989).

  40. R. Kowalski, Logic as a computer language for children, in:European Conf. on Artificial Intelligence (ECAI) (1982) pp. 2–10.

  41. A. Mackworth, J. Mulder and W. Havens, Hierarchical are consistency: Exploiting structured domains in constraint satisfaction problems, Comp. Int. 1 (1985) 118–126.

    Google Scholar 

  42. A.K. Mackworth and E.C. Freuder, The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Art. Int. 25 (1985) 65–73.

    Google Scholar 

  43. E. Mays, C. Apté, J. Griesmer and J. Kastner, Experience with K-Rep: an object centered knowledge representation language, in:Proc. IEEE CAIA-88 (1988) pp. 62–67.

  44. P. Meseguer, Constraint satisfaction problems: An overview, AI Commun. 2 (1989) 3–17.

    Google Scholar 

  45. M. Meyer, Parallel constraint satisfaction in a logic programming framework, in:Proc. Int. Conf. on Parallel Computing Technologies (PaCT-91) (World Scientific, Singapore, 1991) pp. 148–157.

    Google Scholar 

  46. M. Meyer, Using hierarchical constraint satisfaction for lathe-tool selection in a CIM environment, in:5th Int. Symp. on Artificial Intelligence (ISAI'92) (AAAI Press, 1992) pp. 167–177.

  47. M. Meyer, H.-G. Hein and J. Müller, FIDO: Finite domain consistency techniques in logic programming, in:Logic Programming: Proc. 1st and 2nd Russian Conf., ed. A. Voronkov, vol. 592 of LNAI (Springer, 1992) pp. 294–301.

  48. M. Meyer and J. Müller, Weak looking-ahead and its application in computer-aided production planning, in:7th Int. Symp. on Methodologies for Intelligent Systems (ISMIS'93), LNAI (Springer, 1993).

  49. C. Moss, Commercial applications of large Prolog knowledge bases, in:Proc. of the Int. Workshop on Processing Declarative Knowledge (PDK'91), eds. H. Boley and M.M. Richter, vol. 567 in LNAI (Springer, 1991) pp. 32–40.

  50. B. Nebel, Reasoning and revision in hybrid representation systems, PhD thesis, University of Saarbrücken (1989).

  51. P.F. Patel-Schneider, B. Owsnicki-Klewe, A. Kobsa, N. Guarino, R. McGregor, W.S. Mark, D. McGuiness, B. Nebel, A. Schmiedel and J. Yen. Report on the workshop on term subsumption languages in knowledge representation, AI Magazine 11 (1990) 16–23.

    Google Scholar 

  52. L.C. Paulson and A.W. Smith, Logic programming, functional programming, and inductive definitions, in:ELP '91, ed. P. Schroeder-Heister, LNCS 475 (Springer, Berlin/Heidelberg/New York, 1991).

    Google Scholar 

  53. F. Pereira, Can drawing be liberated from the von Neumann style, in:Logic Programming and its Applications, eds. M. van Caneghem and H. Warren, vol. 2 of Ablex series in Artificial Intelligence (1986).

  54. C. Reade,Elements of Functional Programming (Addison-Wesley, 1989).

  55. F. Schmalhofer, O. Kuehn and G. Schmidt, Integrated knowledge acquisition from text, previously solved cases, and expert memories, Appl. Art. Int. 5 (1991) 311–337.

    Google Scholar 

  56. M. Schmidt-Schauß and G. Smolka, Attributive concept descriptions with complements, J. Art. Int. 47 (1991).

  57. A. Schmiedel, A temporal terminological logic, in:Proc. 8th National Conf. on Artificial Intelligence, vol. 2 (AAAI, 1990) pp. 640–645.

    Google Scholar 

  58. W. Stein and M. Sintek, A generalized intelligent indexing method, in:Workshop “Sprachen für KI-Anwendungen, Konzepte — Methoden — Implementierungen”, Bad Honnef (Institute of Applied Mathematics and Computer Science, University of Münster, May 1992).

  59. F. Steinle, HAMLET: Erweiterung eines Constraint-Systems um Negation und Disjunktion und dessen Anbindung an eine Konzeptbeschreibungssprache, Projektarbeit (1993), in German.

  60. C. Walther, A mechanical solution of Schubert's steamroller by many-sorted resolution, Technical Report A31-84, Universität Karlsruhe, Institut für Informatik I, Karlsruhe, Germany (1984).

    Google Scholar 

  61. D.E. Waltz, Generating semantic descriptions of scenes with shadows, Technical Report MAC AI-TR-271, MIT, Cambridge MA (1972).

    Google Scholar 

  62. D.H.D. Warren, An abstract Prolog instruction set, Technical Note 309, SRI International, Menlo Park, CA (October 1983).

    Google Scholar 

  63. A. Yamamoto and H. Tanaka, Translating production rules into a forward reasoning Prolog program. New Generation Comp. 4 (1986) 97 105.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. DFKI., Kaiserslautern, Germany

    Harold Boley, Philipp Hanschke, Knut Hinkelmann & Manfred Meyer

Authors
  1. Harold Boley
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Philipp Hanschke
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Knut Hinkelmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Manfred Meyer
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Supported by BMFT Research Project ARC-TEC (grant ITW 8902 C4)

Rights and permissions

Reprints and permissions

About this article

Cite this article

Boley, H., Hanschke, P., Hinkelmann, K. et al. CoLab: A hybrid knowledge representation and compilation laboratory. Ann Oper Res 55, 9–79 (1995). https://doi.org/10.1007/BF02031716

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02031716

Keywords

Search

Navigation