Mit der aktuellen Überarbeitung der Sprache SDL (Specification and Description Language) der ITU-T wurde die semantische Fundierung der formalen Definition dieser Sprache vollständig überarbeitet; die formale Definition basiert nun auf dem Kalkül der Abstract State Machines (ASMs). Ebenfalls neu definiert wurde das um objekt-orientierte Konzepte erweiterte Datentypsystem. Damit musste eine formale semantische Fundierung für diese neuen Konzepte gefunden werden. Der bisher verwendete Kalkül ACT.ONE sollte nicht mehr verwendet werden, da er schwer verwendbar, nicht implementierbar und nicht auf Objektsysteme erweiterbar ist. In der vorliegenden Arbeit werden die Prinzipien einer formalen Sprachdefinition dargelegt und die Umsetzung dieser Prinzipien für die Sprache SDL-2000 vorgestellt. Dabei wird erläutert, dass eine konsistente Sprachdefinition nur dadurch erreicht werden konnte, dass die Definition der formalen Semantik der Sprache parallel mit der Entwicklung der informalen Definition erfolgte. Dabei deckt die formale Sprachdefinition alle Aspekte der Sprache ab: Syn-tax, statische Semantik und dynamische Semantik. Am Beispiel der Datentypsemantik wird erläutert, wie jeder dieser Aspekte informal beschrieben und dann formalisiert wurde. Von zentraler Rolle für die Anwendbarkeit der formalen Semantikdefinition in der Praxis ist der Einsatz von Werkzeugen. Die Arbeit erläutert, wie aus der formalen Sprachdefinition voll-automatisch ein Werkzeug generiert wurde, das die Sprache SDL implementiert, und wie die durch die Umsetzung der formalen Semantikdefinition in ein Werkzeug Fehler in dieser Definition aufgedeckt und behoben werden konnten. / With the latest revision of ITU-T SDL (Specification and Description Language), the semantic foundations of the formal language definition were completely revised; the formal definition is now based on the calculus of Abstract State Machines (ASMs). In addition, the data type system of SDL was revised, as object-oriented concepts were added. As a result, a new semantical foundation for these new concepts had to be defined. The ACT.ONE calculus that had been used so far was not suitable as a foundation any more, as it is hard to use, unimplementable and not extensible for the object oriented features. In this thesis, we elaborate the principles of a formal language definition, and the realisation of these principles in SDL-2000. We explains that a consistent language definition can only be achieved by developing the formal semantics definition in parallel with the development of the informal definition. The formal language definition covers all aspects of the language: syntax, static semantics, and dynamic semantics. Using the data type semantics as an example, we show how each of these aspects is informally described, and then formalized. For the applicability of the formal semantics definition for practitioners, usage of tools plays a central role. We explain how we transform the formal language definition fully automatically into a tool that implements the language SDL. We also explain how creating the tool allowed us to uncover and correct errors in the informal definition.

Ulm, Univ., Diss., 2007.

In dieser Habilitationsschrift wird die formale Semantik der standardisierten Spezifikationssprache SDL (Specification and Description Language) beschrieben. Da SDL eine sehr umfangreiche Sprache ist, wurde eine repräsentative eingeschränkte Sprache RSDL (Restricted SDL) ausgewählt, um die Konzepte der formalen Definition von SDL darzustellen. Die vorliegende Habilitationsschrift umfaßt zwei große Teile: die Definition der formalen Semantik von RSDL und ihre Implementierung. Die formale Definition der Semantik von RSDL ist verständlich, leicht mit der informalen Beschreibung zu vergleichen und repräsentiert die grundsätzliche Vorstellung von RSDL. Für die Beschreibung werden zwei Teile unterschieden, nämlich die statische Semantik und die dynamische Semantik. Die statische formale Sprachdefinition besteht aus einer konkreten Syntax, einer Menge von Korrektheitsbedingungen, einer Menge von Transformationsregeln und einer abstrakten Syntax als Basis für die dynamische Semantik. Das Ergebnis der statischen Beschreibung ist eine Repräsentation der Spezifikation in abstrakter Syntax. Die Formalisierung der dynamischen Semantik beginnt mit der abstrakten Syntax. Aus dieser abstrakten Syntax wird ein Verhaltensmodell abgeleitet, das auf der mathematischen Theorie der Abstrakten Zustandmaschinen ASM (Abstract State Machines) basiert. Um die Definition der Semantik besonders übersichtlich zu gestalten, wird eine Spezielle Abstrakte Maschine (SAM) unter Nutzung von ASM definiert. Diese abstrakte Maschine stellt eine abstrakte SDL-Maschine dar. Die formale Semantik beschreibt die Eigenschaften von SDL exakt. Um jedoch herauszufinden, ob die Semantik korrekt ist, muß sie mit der Sprachbeschreibung und den Intentionen der Sprachentwickler verglichen werden. Dies geschieht am einfachsten durch eine korrekte Implementierung der Semantik. Die Implementierung der formalen Semantik basiert auf einer Repräsentation der Eingabe als abstrakter Syntaxbaum. Um die Semantik mit minimalem Aufwand zu implementieren, werden existierende Werkzeuge verwendet. Der Compiler wird mit den Standardwerkzeugen lex und yacc generiert. Nach der Syntaxanalyse wird die weitere Verarbeitung über dem abstrakten Syntaxbaum der Eingabe definiert. Die Verarbeitung von abstrakten Syntaxbäumen wird durch ein Werkzeug namens kimwitu erledigt. Mit der hier vorgestellten Technologie wurde die formale Semantik von RSDL implementiert. Entsprechend wird die formale Semantik von SDL implementiert. / In this habilitation thesis the formal semantics of the standardised specification language SDL (Specification and Description Language) is described. Because of the size of the language SDL a representative subset of the language called RSDL (Restricted SDL) was selected to present the concepts of the formal definition. In this thesis two major parts are covered: the definition of the formal semantics and its implementation. The RSDL formal semantics is intelligible, easily comparable with the informal description and represents the general understanding of RSDL. We distinguish between two phases of the definition, namely the static semantics and the dynamic semantics. The static semantics comprises the definition of a concrete grammar, a set of correctness constraints, a set of transformation rules and an abstract syntax as basis for the dynamic semantics. The result of the static semantics is a representation of the specification in abstract syntax. The dynamic semantics starts with the abstract syntax. From here a behaviour model is derived based on the theory of Abstract State Machines (ASM). In order to keep the presentation intelligible a special abstract machine is defined using ASM. This abstract machine in fact represents an abstract SDL-machine. The formal semantics describes the properties of SDL exactly. However, in order to check the correctness of the formalisation, it has to be compared with the informal language description and the intentions of the language designers. This is most easily done using a correct implementation of the semantics. The implementation of the semantics is based on a representation of the input as an abstract syntax tree. For implementing the semantics with minimal effort existing tools are used. The compiler is produced using the standard tools lex and yacc. After parsing the remaining processing is defined over abstract syntax trees, which is covered by a tool called kimwitu. The formal semantics of RSDL is implemented using these tools. The same approach is applicable for SDL.

In this thesis we see two new approaches to compose tree transducers and more general to fuse functional programs. The first abroach is based on initial algebras. We prove a new variant of the acid rain theorem for mutually recursive functions where the build function is substituted by a concrete functor. Moreover, we give a symmetric form (i.e. consumer and producer have the same syntactic form) of our new acid rain theorem where fusion is composition in a category and thus in particular associative. Applying this to compose top-down tree transducers yields the same result (on a syntactic level) as the classical top-down tree transducer composition. The second approach is based on free monads and monad transformers. In the same way as monoids are used in the theory of character string automata, we use monads in the theory of tree transducers. We generalize the notion of a tree transducer defining the monadic transducer, and we prove an according fusion theorem. Moreover, we prove that homomorphic monadic transducers are semantically equivalent. The latter makes it possible to compose syntactic classes of tree transducers (or particular functional programs) by simply composing endofunctors.

The original and still a major purpose of ontologies in computer and information sciences is to serve for the semantic integration of represented content, facilitating information system interoperability. Content can be data, information, and knowledge, and it can be distributed within or across these categories. A myriad of languages is available for representation. Ontologies themselves are artifacts which are expressed in various languages. Different such languages are utilized today, including, as well-known representatives, predicate logic, subsuming first-order (predicate) logic (FOL), in particular, and higher-order (predicate) logic (HOL); the Web Ontology Language (OWL) on the basis of description logics (DL); and the Unified Modeling Language (UML). We focus primarily on languages with formally defined syntax and semantics. This overall picture immediately suggests questions of the following kinds: What is the relationship between an ontology and the language in which it is formalized? Especially, what is the impact of the formal semantics of the language on the formalized ontology? How well understood is the role of ontologies in semantic integration? Can the same ontology be represented in multiple languages and/or in distinct ways within one language? Is there an adequate understanding of whether two expressions are intensionally/conceptually equivalent and whether two ontologies furnish the same ontological commitments? One may assume that these questions are resolved. Indeed, the development and adoption of ontologies is widespread today. Ontologies are authored in a broad range of different languages, including offering equally named ontologies in distinct languages. Much research is devoted to techniques and technologies that orbit ontologies, for example, ontology matching, modularization, learning, and evolution, to name a few. Ontologies have found numerous beneficial applications, and hundreds of ontologies have been created, considering solely the context of biomedical research. For us, these observations increase the relevance of the stated questions and close relatives thereof, and raise the desire for solid theoretical underpinnings. In the literature of computer and information sciences, we have found only few approaches that tackle the foundations of ontologies and their representation to allow for answering such questions or that actually answer them. We elaborate an analysis of the subject as the first item of central contributions within this thesis. It mainly results in the identification of a vicious circularity in (i) the intended use of ontologies to mediate between formal representations and (ii) solely exploiting formal semantic notions in representing ontologies and defining ontology-based equivalence as a form of intensional/conceptual equivalence. On this basis and in order to overcome its identified limitations, we contribute a general model-theoretic semantic account, named \\\"ontological semantics\\\". This kind of semantics takes the approach of assigning arbitrary entities as referents of atomic symbols and to link syntactic constructions with corresponding ontological claims and commitments. In particular, ontological semantics targets the avoidance of encoding effects in its definition. Therefore we argue that this semantic account is well suited for interpreting formalized ontologies and for defining languages for the representation of ontologies. It is further proposed as a fundament for envisioned novel definitions of the intensional equivalence of expressions, in potential deviation from only being formally equivalent under set-theoretic semantics. The thesis is defended that a particular usage of a formalism and its respective vocabulary should be accompanied by establishing an ontological semantics that is tailored to that use of the formalism, in parallel to the formal semantics of the language, in order to capture the ontological content of the formal representation for adequate reuse in other formalisms. Accordingly, we advocate ontological semantics as a useful framework for justifying translations on an intensional basis. Despite all deviations of ontological semantics from its set-theoretic blueprint, close relationships between the two can be shown, which allow for using established FOL and DL reasoners while assuming ontological semantics.

The original and still a major purpose of ontologies in computer and information sciences is to serve for the semantic integration of represented content, facilitating information system interoperability. Content can be data, information, and knowledge, and it can be distributed within or across these categories. A myriad of languages is available for representation. Ontologies themselves are artifacts which are expressed in various languages. Different such languages are utilized today, including, as well-known representatives, predicate logic, subsuming first-order (predicate) logic (FOL), in particular, and higher-order (predicate) logic (HOL); the Web Ontology Language (OWL) on the basis of description logics (DL); and the Unified Modeling Language (UML). We focus primarily on languages with formally defined syntax and semantics. This overall picture immediately suggests questions of the following kinds: What is the relationship between an ontology and the language in which it is formalized? Especially, what is the impact of the formal semantics of the language on the formalized ontology? How well understood is the role of ontologies in semantic integration? Can the same ontology be represented in multiple languages and/or in distinct ways within one language? Is there an adequate understanding of whether two expressions are intensionally/conceptually equivalent and whether two ontologies furnish the same ontological commitments? One may assume that these questions are resolved. Indeed, the development and adoption of ontologies is widespread today. Ontologies are authored in a broad range of different languages, including offering equally named ontologies in distinct languages. Much research is devoted to techniques and technologies that orbit ontologies, for example, ontology matching, modularization, learning, and evolution, to name a few. Ontologies have found numerous beneficial applications, and hundreds of ontologies have been created, considering solely the context of biomedical research. For us, these observations increase the relevance of the stated questions and close relatives thereof, and raise the desire for solid theoretical underpinnings. In the literature of computer and information sciences, we have found only few approaches that tackle the foundations of ontologies and their representation to allow for answering such questions or that actually answer them. We elaborate an analysis of the subject as the first item of central contributions within this thesis. It mainly results in the identification of a vicious circularity in (i) the intended use of ontologies to mediate between formal representations and (ii) solely exploiting formal semantic notions in representing ontologies and defining ontology-based equivalence as a form of intensional/conceptual equivalence. On this basis and in order to overcome its identified limitations, we contribute a general model-theoretic semantic account, named \\\"ontological semantics\\\". This kind of semantics takes the approach of assigning arbitrary entities as referents of atomic symbols and to link syntactic constructions with corresponding ontological claims and commitments. In particular, ontological semantics targets the avoidance of encoding effects in its definition. Therefore we argue that this semantic account is well suited for interpreting formalized ontologies and for defining languages for the representation of ontologies. It is further proposed as a fundament for envisioned novel definitions of the intensional equivalence of expressions, in potential deviation from only being formally equivalent under set-theoretic semantics. The thesis is defended that a particular usage of a formalism and its respective vocabulary should be accompanied by establishing an ontological semantics that is tailored to that use of the formalism, in parallel to the formal semantics of the language, in order to capture the ontological content of the formal representation for adequate reuse in other formalisms. Accordingly, we advocate ontological semantics as a useful framework for justifying translations on an intensional basis. Despite all deviations of ontological semantics from its set-theoretic blueprint, close relationships between the two can be shown, which allow for using established FOL and DL reasoners while assuming ontological semantics.:* Preface ** Abstract ** Contents ** Acknowledgments ** Foreword 1 Introduction 1.1 Background 1.2 Motivations 1.3 Theses, Objectives and Scope 1.4 Outline and Contributions 1.5 Formal Preliminaries 2 Foundations on Languages, Semantics, and Ontology 2.1 Formal Syntax and Formal Semantics 2.2 The Role of Ontologies in Semantic Integration 2.3 Ontological Analysis and Meta-Ontological Architecture 2.4 Conceptualization of Categories and Relations - CR 2.5 Summary of the Analysis and Next Steps 3 Views on Set-Theoretic Semantics of Classical Predicate Logics 3.1 Tarskian Model Theory and Set-Theoretic Superstructure 3.2 Formal Semantics and Choices for Entity Postulation 3.3 Theory View of Semantics 3.4 Aims for an Ontologically Neutral Semantic Account 4 Ontological Semantics 4.1 Definition of Ontological Structures by Analogy to the Set-Theoretic Approach 4.2 Properties and Further Background for Ontological Structures in General 4.3 Ontological Models & Signature Aspects 4.4 Semantics of Predication 4.5 Semantics of Connectives and Quantifiers & Semantic Notions 4.6 Relations between Ontological and Set-Theoretic Semantics 4.7 Ontological Neutrality 5 Ontological Engineering and Applications 5.1 Formalization Method for Ontology Representation in FOL 5.2 Ontological Usage Schemes 5.3 Glimpse on Characterizing Modular Representation 5.4 Applications in the Biomedical Domain 6 Contributions to Ontologies 6.1 Formalizations of Categories and Relations - CR 6.2 Remarks on Further Contributions 6.3 Ontologies of Time 7 Conclusion and Continuation 7.1 Resume 7.2 Related Work 7.3 Conclusions 7.4 Beginnings of Future Work Appendix A Additional Preliminaries A.1 Logical Notions A.2 Axiomatic Systems of Set and Number Theory B Axioms of the CR Taxonomy in OWL B.1 Asserted OWL Class Axioms B.2 Asserted OWL Object Property Axioms C Lists of Figures and Tables C.1 List of Figures C.2 List of Tables D Abbreviations, Acronyms and Names D.1 Abbreviations D.2 Acronyms and Names E References E.1 Literature References E.2 Web References/List of URLs F Work and Author Information ** Selbständigkeitserklärung (Declaration of Authorship) ** Bibliographic Data ** Scientific Record

In this thesis we see two new approaches to compose tree transducers and more general to fuse functional programs. The first abroach is based on initial algebras. We prove a new variant of the acid rain theorem for mutually recursive functions where the build function is substituted by a concrete functor. Moreover, we give a symmetric form (i.e. consumer and producer have the same syntactic form) of our new acid rain theorem where fusion is composition in a category and thus in particular associative. Applying this to compose top-down tree transducers yields the same result (on a syntactic level) as the classical top-down tree transducer composition. The second approach is based on free monads and monad transformers. In the same way as monoids are used in the theory of character string automata, we use monads in the theory of tree transducers. We generalize the notion of a tree transducer defining the monadic transducer, and we prove an according fusion theorem. Moreover, we prove that homomorphic monadic transducers are semantically equivalent. The latter makes it possible to compose syntactic classes of tree transducers (or particular functional programs) by simply composing endofunctors.