Proceedings of the 2005 Australasian Ontology Workshop - Volume 58

title: Sydney OWL Syntax - towards a Controlled Natural Language Syntax for OWL 1.1
abstract: This paper describes a proposed new syntax that can be used to write and read OWL ontologies in Controlled Natural Language (CNL): a well-defined subset of the English language. Following the lead of Manchester OWL Syntax in making OWL more accessible for non-logicians, and building on the previous success of Schwitter’s PENG (Processable English), the proposed Sydney OWL Syntax enables two-way translation and generation of grammatically correct full English sentences to and from OWL 1.1 functional syntax. Used in conjunction with OWL tools, it is designed to facilitate ontology construction and editing by enabling authors to write an OWL ontology in a defined subset of English. It also improves readability and understanding of OWL statements or whole ontologies, by enabling them to be read as English sentences. It is hoped that by providing the option of an intuitive, easy to use English syntax which requires no specialized knowledge, the broader community will be far more likely to develop and benefit from Semantic Web applications. This paper is a discussion paper covering the scope, design, and examples of Sydney OWL Syntax in use, and the authors invite feedback on all aspects of the proposal via email to krr.sydneysyntax@cse.unsw.edu.au. Working drafts of the full specification are available at http://www.ics.mq.edu.au/~rolfs/sos.

title: Next Steps in Propositional Horn Contraction
abstract: Standard belief contraction assumes an underlying logic containing full classical propositional logic, but there are good reasons for considering contraction in less expressive logics. In this paper we focus on Horn logic. In addition to being of interest in its own right, our choice is motivated by the use of Horn logic in several areas, including ontology reasoning in description logics. We consider three versions of contraction: entailment-based and inconsistency-based contraction (e-contraction and i-contraction, resp.), introduced by Delgrande for Horn logic, and package contraction (p-contraction), studied by Fuhrmann and Hansson for the classical case. We show that the standard basic form of contraction, partial meet, is too strong in the Horn case. We define more appropriate notions of basic contraction for all three types above, and provide associated representation results in terms of postulates. Our results stand in contrast to Delgrande's conjectures that orderly maxichoice is the appropriate contraction for both e- and i-contraction. Our interest in p-contraction stems from its relationship with an important reasoning task in ontological reasoning: repairing the subsumption hierarchy in EL. This is closely related to p-contraction with sets of basic Horn clauses (Horn clauses of the form p → q). We show that this restricted version of p-contraction can also be represented as i-contraction.

title: Admissible and Restrained Revision
abstract: As partial justification of their framework for iterated belief revision Darwiche and Pearl convincingly argued against Boutilier's natural revision and provided a prototypical revision operator that fits into their scheme. We show that the Darwiche-Pearl arguments lead naturally to the acceptance of a smaller class of operators which we refer to as admissible. Admissible revision ensures that the penultimate input is not ignored completely, thereby eliminating natural revision, but includes the Darwiche-Pearl operator, Nayak's lexicographic revision operator, and a newly introduced operator called restrained revision. We demonstrate that restrained revision is the most conservative of admissible revision operators, effecting as few changes as possible, while lexicographic revision is the least conservative, and point out that restrained revision can also be viewed as a composite operator, consisting of natural revision preceded by an application of a "backwards revision" operator previously studied by Papini. Finally, we propose the establishment of a principled approach for choosing an appropriate revision operator in different contexts and discuss future work.

title: Merging Epistemic States
abstract: Intelligent agents are often faced with the problem of trying to merge possibly conflicting pieces of information obtained from different sources into a consistent view of the world. We propose a framework for the modelling of such merging operations with roots in the work of Spohn . Unlike most approaches we focus on the merging of epistemic states, not knowledge bases. We construct a number of plausible merging operations and measure them against various properties that merging operations ought to satisfy. Finally, we discuss the connection between merging and the use of infobases , .

title: Implementing Iterated Belief Change Via Prime Implicates
abstract: Belief change is concerned with modelling the way in which an idealised (rational) reasoner maintains their beliefs and the way in which those beliefs are modified as the reasoner acquires new information. The AGM [1,3,5] framework is the most widely cited belief change methodology in the literature. It models the reasoner’s belief state as a set of sentences that is logically closed under deduction and provides for three belief change operations: expansion, contraction and revision. Each of the AGM belief change operations is motivated by principles of rationality that are formalised by way of rationality postulates.

title: TAS and IsaWin: Generic Interfaces for Transformational Program Development and Theorem Proving
abstract: We present a new approach to the implementation of graphical user interfaces (GUIs) for formal program development systems like transformation systems or interactive theorem provers. Its distinguishing feature is a generic, open system design which allows the development of a family of tools for different formal methods on a sound logical basis with a uniform appearance. The context of this work is the UniForM project [KPO+95], the aim of which is to develop a framework integrating different formal methods in a logically consistent way. Consistency is achieved by encoding formal methods such as CSP and Z in the theorem prover Isabelle [Pau94], which is used to perform the program development as well as to prove the correctness of the transformation rules. One of the main UniForM objectives is to enable non-expert users to actually perform at least part of the developmen~ themselves. Hence there is a crucial need for an encapsulation technique of these Isabelle encodings providing a generic way of building graphical user interfaces.

title: Tactic-Based Optimized Compilation of Functional Programs
abstract: Within a framework of correct code-generation from HOL-specifications, we present a particular instance concerned with the optimized compilation of a lazy language (called MiniHaskell) to a strict language (called MiniML). 
 
Both languages are defined as shallow embeddings into denotational semantics based on Scott's cpo's, leading to a derivation of the corresponding operational semantics in order to cross-check the basic definitions. 
 
On this basis, translation rules from one language to the other were formally derived in Isabelle/HOL. Particular emphasis is put on the optimized compilation of function applications leading to the side-calculi inferring e.g. strictness of functions. 
 
The derived rules were grouped and set-up as an instance of our generic, tactic-based translator for specifications to code.

title: A Real-Time Low-Power Stereo Vision Engine Using Semi-Global Matching
abstract: Many real-time stereo vision systems are available on low-power platforms. They all either use a local correlation-like stereo engine or perform dynamic programming variants on a scan-line. However, when looking at high-performance global stereo methods as listed in the upper third of the Middlebury database, the low-power real-time implementations for these methods are still missing. We propose a real-time implementation of the semi-global matching algorithm with algorithmic extensions for automotive applications on a reconfigurable hardware platform resulting in a low power consumption of under 3W. The algorithm runs at 25Hz processing image pairs of size 750x480 pixels and computing stereo on a 680x400 image part with up to a maximum of 128 disparities.

title: Multimedia synchronization techniques: experiences based on different system structures
abstract: Multimedia synchronization" is needed to ensure a temporal ordering of events in multimedi a systems . There are two parts to this problem : the definition of temporal relationships among audio , video, and other data ; and the delivery of the data in accordance with these relationships . It i s important to distinguish between liveand synthetic-synchronization . Live-synch, deals with th e presentation of information in the same order as it was originally collected . For synthetic-synch . various pieces of information must be properly ordered and synchronized in time . Based on th e experiences in DiME and HeiTS, we document the implications of using a hybrid or a unified syste m structures on the required techniques for implementing synchronization .

title: On algorithmically checking whether a Hilbert series comes from a complete intersection
abstract: It is not possible to determine from the Hilbert series whether a commutative Z-graded Noetherian algebra is a complete intersection. Nevertheless, the Hilbert series of a complete intersection satisfies very stringent conditions and we define a concept CI-type for formal power series, that embodies some of these necessary properties. This definition becomes interesting mainly for algebras that are not standard i.e. not generated in degree 1. For the class of formal power series that occur as the Hilbert series of Z-graded Noetherian Cohen-Macaulay algebras, the main result is a criterion for a series to be of CI-type, that is formulated in terms of properties of truncated power series. Hence it can be used as the basis for an algorithm that provides in a finite number of steps either a rational function expression of the formal power series, or the information that the truncated power series is not of CI-type. Also sample computations using this algorithm on some non-standard graded invariant algebras are described.