a

Formal Aspects of Computer Science

  

 

18 Jan 2001: This section is outdated  and is in the process of being updated.

Headed by Prof J Heidema

Primary Focus Areas

While the aim in our formal teaching is to provide a broad basis of knowledge and skills, the formal aspects on which our research (including M- and D-supervision) currently focuses, fall under the description of  Knowledge Representation and Reasoning, and includes applied logic, automated reasoning, graph grammars, and AI.

Applied Logic (logic seen from the perspective of computing and AI) involves purpose-built formal languages designed to permit the representation of knowledge about specific systems. It is also known to enable the formalization of defensible reasoning, in which the evidence supports conclusions only tentatively, and the legitimacy of basing hypotheses on experimental results has been re-established.

Logics of belief;
Formal deductive systems;
Temporal logic;
Non-monotonic logic;
Verisimilitude; and
Preparation of study material for use with a textbook on applied logic.

People involved include -

  • Arina Britz
  • Prof I Burger (RAU)
  • Johannes Heidema
  • Tertia Hörne
  • Prof WA Labuschane (Otago)
  • Louise Leenen
  • Dr TA Meyer (UP)
  • Marianne Loock
  • Laurette Pretorius
  • Alta van der Merwe
  • Biffie van der Merwe
  • FACSLAB (UCT)
Automated Reasoning research includes identifying a set of usable heuristics for proving properties of a formal specification written in a set-theoretic-like language such as Z, using the resolution-based theorem prover OTTER
People involved include André van der Poll

Graph Grammars. Graphs present us with a well-defined mathematical approach to model two-dimensional knowledge, while graph grammars provide an equally powerful model that permits reasoning, investigating and changing current knowledge. Our research involves the application and extension of these notions to facilitate the presentation of and reasoning about three-dimensional spatial configurations, for example chemical structures.
People involved include -

  • Andries Barnard
  • Prof EM Ehlers (RAU)
Artificial Intelligence. The research in AI centres around agents, their epistemic states, beliefs and belief change. Relations between e.g. belief change, non-monotonic logic and verisimilitude are investigated.
Persons involved: As for Applied logic.

Formal Teaching  Aspects

  • Theoretical computer science: COS101, COS201, COS301
  • Logic: COS161, COS261, COS361, COS407
  • Artificial Intelligence (AI): COS351, COS451, COS452
  • Computability: COS405
  • Algorithm design and Complexity: COS408, COS409
  • Formal program verification: COS492
  • Theory of programming languages: COS416, COS417

Presentations & Publications

Arina Britz

  • Britz, K: "Relations and programs", M.Sc thesis, University of Stellenbosch, 1988.
  • Britz, K: "Power Constructs and Propositional Systems", Ph.D thesis, University of Cape Town, 1999.
  • Britz, K: "A relational theory of computation", Manuscript, University of Stellenbosch, 1987.
    Britz, K: "A Temporal logic for program verification", Manuscript, University of Stellenbosch, 1987.
  • Britz, K: "Peirce algebras", Interdisciplinary Logic Conference, Durban, 1987.
  • Britz, K: " A relational theory of computation", 2nd Annual conference for MSc and PhD students in Computer Science, University of Stellenbosch, Stellenbosch, 1987.
  • Britz, K: "Fuzzy power relations", Annual Conference of the South African Mathematical Society, University of Pretoria, Pretoria, 1991.
  • Britz, K: "A parameterized verisimilar ordering", Workshop on Verisimilitude, UNISA, Pretoria, 1994.
  • Britz, K: "A power algebra for theory change", Joint Conference of the SAMS, AMS, LMS and SAMSA, University of Pretoria, Pretoria, 1997.
  • Britz, K: " Ordering formula sets", 41st Annual Conference of the South African Mathematical Society, Rand Afrikaans University, 1998.
  • Britz, K. and C. Brink: "Relating, and operating on, formula sets", 4th International Seminar on Relational Methods in Logic, Algebra and Computer Science", Warsaw, Poland, 1998.
  • Britz, K: "A new semantics for the Logic of Paradox", 42nd Annual Conference of the South African Mathematical Society, University of the North, Pietersburg, 1999.
  • Britz, K., C. Brink and A. Melton: "A note on fuzzy power relations", Fuzzy sets and systems, Vol 54, No 1, 1993, pp 115-118.
  • Britz, K. and C. Brink: "Computing verisimilitude", Notre Dame Journal of Formal Logic, Vol 36, No 1, 1995, pp. 30 - 43.
  • Brink, K: "A power algebra for theory change", Journal of Logic, Language, and Information. To appear.
  • Brink, C. and K. Britz: "A note on verisimilitude and irrelevance", Liber Amicorum for Johan van Benthem, CSLI, 1999.
  • Britz, K., C. Brink and R.A. Schmidt: "Peirce algebras", Formal Aspects of Computing, No 6, 1993, pp 339 - 358.

Andre van der Pol

  • Heuristics for Resolution-based Set-theoretic Proofs, Journal: SACJ, Issue 23, pp 3 -17, 1999
  • SAMS, RAU, 1998, Heuristics for Resolution-based Set-theoretic Proofs.
    3rd Annual workshop on Theorem proving and Model checking, UCT, 1998, Heuristics for Resolution-based Set-theoretic Proofs.
  • Software Metrics for Procedural Programs (1988)
  • Introduction to the Z Specification language (1993)\
  • Heuristics for Resolution-based Set-theoretic Proofs (1998)

  Ruth De Villiers 

  • M.R. de Villiers & P. Kotze Applying Software Engineering Methods to Instructional Systems Development. Article in the South African Computer Journal, No 20, August 1997.
  • M.R. de Villiers Instructional theories of experts: a practical implementation. Article in the South African Journal of Higher Education. Vol 12 (2), 1998.
  • M.R. de Villiers FRAMES: A User-controlled Practice Environment in Theoretical Computer Science. Paper (accepted but not delivered) at ED-MEDIA World Conference on Educational Multimedia and Hypermedia, Boston, USA, June 1996.
  • M.R. de Villiers A Component-Based Interactive Practive Environment. Paper at 3rd International CALISCE '96 (Computer Aided learning and Instruction in Science and Engineering) Conference, San Sebastion, Spain, July 1996.
  • M.R. de Villiers & P. Kotze Factors underlying the Design and Development of Interactive Computer-Based Learning and Instructional Systems. Paper at the Fourth CBE/CBT Conference and Workshop of CENSE (Centre for Software Engineering), Unisa, Pretoria, October 1996.
  • M.R. de Villiers Applying the Hexa-C Metamodel of Instructional Theory and Design Educational Web Applications. Paper at WebNet 99 Conference, Honolulu, Hawaii, USA, October 1999.
  • M.R. de Villiers Evaluation of an Interactive Learning Environment using the Hexa-C Metamodel. Paper at ICCE99 (7th International Conference on Computers in Education), Chiba, Japan, November 1999.
    M.R. de Villiers: Spreadsheets in Mathematics Tuition. Paper at the Second ISC Computer Users' Conference, Pretoria 1993.
  • M.R. de Villiers Integrating a Software Engineering Approach with Instructional Factors in the Development of Instructional Systems - in short: S E + I D in I S D. Poster presentation at SAICSIT.95 (South African Institute for Computer Scientists and Information Technologists) Symposium, Pretoria 1995.
  • M.R. de Villiers & P. Kotze Software Engineering Development Methodologies applied to Computer-Aided Instruction. Paper at SAICSIT 96 (South African Institute for Computer Scientists and Information Technologists) Annual Research and Development Symposium, Durban. September 1996.
  • M.R. de Villiers Component-Based Instructional Software. Paper at SACLA '96 (Southern African Computer Lecturers' Association) Conference, Johannesburg-Pretoria area, June 1996.
  • M.R. de Villiers Instructional Design for Computer-Assisted Instruction. Paper at the Fourth CBE/CBT Conference and Workshop of CENSE (Centre for Software Engineering), Unisa, Pretoria, October 1996.
  • M.R. de Villiers: Structured Knowledge Representation with Particular Reference to Frames. Unpublished Special Topic Report, Department of Computer Science, University of South Africa, Pretoria, 1989.
  • M.R. de Villiers: Relations: A CAI Tutorial in Theoretical Computer Science. Unpublished MEd mini-dissertation, University of Pretoria, Pretoria, 1993.
  • M.R. de Villiers Integrating a Software Engineering Approach and Instructional Factors in Instructional Software Development - illustrated by a Prototype in Theoretical Computer Science. Unpublished MSc dissertation, University of South Africa, Pretoria, 1995.
Ken Halland
  • KJ Halland,  Circumscriptive Reasoning, MSc Dissertation
  • K J Halland and WA Labuschagne ,A family tree of circumscriptive logics.  SACJ No 14 of 1995. 

Paula Kotzé

  • Kotzé P; Towards an option space for interactive teaching systems. Invited address at the Artificial Intelligence in Education Seminar, Department of Psychology, University of Nottingham (UK), 14 July 1994.

Louise Leenen

  • Leenen L: "Contributions towards an implementation of a Branch-and-cut algorithm for the travelling salesman problem", MSc Thesis, RAU 1993. 
  • Leenen L: "Die oplossing van die simmetriese handelsreisigersprobleem d.m.v. die byvoeging van newe-beperkings", Fifth National MSc-PhD Conference at Katberg, Ciskei, August 1990.
  • Leenen L: "Solving the travelling salesman problem using the Branch-and-cut method", SACLA, 1991.
  • Leenen L: THC Smith en TWS Meyer: "An efficient primal simplex implementation for the continuous 2-matching problem", South African Computer Journal 5 1991 (28-31).
  • Leenen L: "Die oplossing van die simmetriese handelsreisigersprobleem d.m.v. die byvoeging van newe-beperkings", Fifth National MSc-PhD Conference at Katberg, Ciskei, August 1990.
  • Leenen L and THC Smith: "An efficient dual simplex implementation for the continuous 2-matching problem with side constraints", 14th International Symposium on Mathematical Programming, August 1991.
  • Leenen L and THC Smith: "Solving the travelling salesman problem using the branch-and-cut method", SACLA, 1991.
  • Leenen L: "Solving the Travelling Salesman Problem using the Cut-and-branch Method" - UNISA, Department of Computer Science and Information Systems Colloquium, 21 Augustus, 1991.
  • Leenen L: Presented a seminar on Computability, Department of Computer Science and Information Systems, 1994.

Linda Miller

  • Miller, M G: The Frame Problem, Unisa 1994 (MSc).
  • Miller, M G: The Situation Calculus - MSc/PhD konferensie te Stellenbosch, Desember 1994.
  • Labuschagne, W A and Miller, M G : On Using the Situation Calculus Dynamically Rather Than Temporally, South Afican Computer Journal, Number 12, November 1994.

Elsa Naudè

  • Naudè, E J: Contributions to an expert system for the interactive modelling of linear models. SACLA. 24/06/1996.
  • Naudè, E.J: An Expert System for linear regression analysis. MSc/PhD-konferensie. Espada Ranch, RSA. 26/06/96.

Rita Nienaber

  • R C Nienaber: Microcomputer Applications, 1st ed. 1992, 2nd ed. 1995, 3rd ed. 1996.
  • R C Nienaber & E A van Wyk: Microcomputer Skills, 1997.
  • R C Nienaber: Report on Approaches and Lecturing of Information Systems at Technikons, Premos Pretoria, TECLA Kongres, 18 Maart 1997.