Fundamenta Informaticae - Volume 40, issue 1

Authors: Ambainis, Andris | Freivalds, Rūsiņš | Smith, Carl H.

Article Type: Research Article

Abstract: In this paper, we reconsider the definition of procrastinating learning machines. In the original definition of Freivalds and Smith [FS93], constructive ordinals are used to bound mindchanges. We investigate possibility of using arbitrary linearly ordered sets to bound mindchanges in similar way. It turns out that using certain ordered sets it is possible to define inductive inference types different from the previously known ones. We investigate properties of the new inductive inference types and compare them to other types.

DOI: 10.3233/FI-1999-40101

Citation: Fundamenta Informaticae, vol. 40, no. 1, pp. 1-16, 1999

Authors: Doherty, Patrick | Kachniarz, Jarosław | Szałas, Andrzej

Article Type: Research Article

Abstract: We introduce the notion of a meta-query on relational databases and a technique which can be used to represent and solve a number of interesting problems from the area of knowledge representation using logic. The technique is based on the use of quantifier elimination and may also be used to query relational databases using a declarative query language called SHQL (Semi-Horn Query Language), introduced in [6]. SHQL is a fragment of classical first-order predicate logic and allows us to define a query without supplying its explicit definition. All SHQL queries to the database can be processed in polynomial time (both …on the size of the input query and the size of the database). We demonstrate the use of the technique in problem solving by structuring logical puzzles from the Knights and Knaves domain as SHQL meta-queries on relational databases. We also provide additional examples demonstrating the flexibility of the technique. We conclude with a description of a newly developed software tool, The Logic Engineer, which aids in the description of algorithms using transformation and reduction techniques such as those applied in the meta-querying approach. Show more

Keywords: knowledge representation, query languages, relational databases

DOI: 10.3233/FI-1999-40102

Citation: Fundamenta Informaticae, vol. 40, no. 1, pp. 17-30, 1999

Authors: Johnson, C.A.

Article Type: Research Article

Abstract: Cyclic covers are shown to characterise disjunctive stable models of unstratified deductive databases, and to facilitate top-down query processing, query compilation and view updating under the disjunctive stable model semantics. Such processing is shown to be more complex than comparable processing of stratified databases.

Keywords: Disjunctive deductive databases, disjunctive stable models, cyclic covers, query processing, query compilation, view updates

DOI: 10.3233/FI-1999-40103

Citation: Fundamenta Informaticae, vol. 40, no. 1, pp. 31-51, 1999

Authors: Preoteasa, Viorel

Article Type: Research Article

Abstract: Using a categorical model of abstract data types [2, 3, 13, 15], we show, following the Kozen's technique [10] and Tarjan's constructions for a deterministic automaton [16], that if two unambiguous regular expressions define the same regular language, then they represent two isomorphic abstract data types.

Keywords: abstract data types, categorical model, unambiguous regular expressions, finite automata

DOI: 10.3233/FI-1999-40104

Citation: Fundamenta Informaticae, vol. 40, no. 1, pp. 53-77, 1999

Authors: Su, Kaile | Li, Wei

Article Type: Research Article

Abstract: In Reiter's default logic, the operator in the fixed-point definition of extension is not appropriate to compute extensions by its iterated applications. This paper presents a class of alternative operators, called compatible ones, such that, at least for normal default theories and so-called well-founded, ordered default theories, we can get extensions by iterated applications of them. In addition, we completely answer Etherington's conjectures about both his procedure for generating extensions and a modified version of it. In particular, we give an example of a finite, ordered default theory, for which the original procedure fails to converge, and show that the …computation of the modified one is essentially the iteration of a compatible operator and converges for finite, ordered theories. Show more

Keywords: reasoning, knowledge representation, default logic, ordered default theory, extension

DOI: 10.3233/FI-1999-40105

Citation: Fundamenta Informaticae, vol. 40, no. 1, pp. 79-102, 1999