Module extraction is an important reasoning task, aiding in the design, reuse and maintenance of ontologies. Reasoning services such as subsumption testing and MinA extraction have been shown to bene t from module extraction methods. Though various syntactic traversal-based module extraction algorithms exist for extracting modules, many only consider the subsumee of a subsumption statement as a selection criterion for reducing the axioms in the module. In this dissertation we extend the bottom-up reachability-based module extraction heuristic for the inexpressive Description Logic EL, by introducing a top-down version of the heuristic which utilises the subsumer of a subsumption statement as a selection criterion to minimize the number of axioms in a module. Then a combined bidirectional heuristic is introduced which uses both operands of a subsumption statement in order to extract very small modules. We then investigate the relationship between MinA extraction and bidirectional reachabilitybased module extraction. We provide empirical evidence that bidirectional reachability-based module extraction for subsumption entailments in EL provides a signi cant reduction in the size of modules for almost no additional costs in the running time of the original algorithms. / Computer Science / M. Sc. (Computer Science)

This is a theoretical and empirical study of leadership. Although sociologists have contributed important theories and research on authority and power, there is not yet a developed leadership theory in sociology. On the other hand, leadership studies in other disciplines are not satisfying, and they will not be satisfying in the foreseeable future if they adhere to their basic theoretical orientations, e.g. focusing on leadership personal traits and characteristics. I elaborate the important sociological theories that can be used in the study of leadership. I also intend to link sociological theories of leadership to social background analysis. The social backgrounds considered are family status, education, religion, military service, and more. Particular attention is paid to military background and its impact on business, because military has always been such an important social phenomenon but the theories of it have been controversial.The study of leadership inevitably involves both individuals and their groups. With evidence obtained from different data sources on leaders and on business organizations, I studied the impact of military social background of business leaders. This research unpacks the rise of business leaders with military experience in the late 20th century, using a database on the 20th century Great American Business Leaders. This research also measures the organizational performance of these leaders, incorporating information from Standard & Poor's Compustat database. Statistical techniques like logistic regressions and hierarchical linear models are used in the analysis to test various effects on personal and organizational performance. I found that military experience does not help a business leader in aspects like time taken to become a CEO and time to be a CEO, but it does help organizational performance as measured by profitability. Both rank and number of years in the military contribute to profitability. I also found that ex-military business leaders differ from non-military business leaders in certain organizational behaviors, e.g. they are less likely to downsize the organizations.The theory of institutional logics and social background analysis were combined in this study. I also attempted to link institutional logics with theories of rationality. From the idea of institutional leadership and inter-institutional relationship, I suggested a theory of extended rationality.

During the first decade of the twenty-first century, the Swedish civil service underwent some extensive changes, such as the relocations of public sector jobs, initiated by the government in 2005. This thesis follows an ethnological tradition of focusing on employees’ perspectives as a way of exploring power relations and changes in society. In this study, I draw attention to the fears, joys, anxieties, hopes, and dreams of employees in the Swedish civil service at a time when their workplace was being relocated from one city to another. The study especially focuses on the fact that a decision to relocate initiates processes that change employee’s images of their work life and future. They become forced to rethink life and work and re-identify with professional positions. Such processes are described in this thesis as processes of professional identification. The aim of the study is to analyze professional identification among employees during the relocation of a government agency. It is based on four articles that highlight different aspects of the relocation and the conditions under which research was conducted. The overarching question that runs through the thesis is: what did processes of professional identification mean in relocation practice? I argue that such processes should be taken into account as pivotal to civil service practices such as relocation work. Such knowledge could also be used as a tool for thinking about work life change in a wider sense. Because relocations entail moving people’s entire lives, points of interest are formulated that tell stories of how social norms and rules are formed, maintained, and contested. The results in this thesis could also serve as a departure for discussing the localization of knowledge-intensive institutions. The case study builds on ethnographic fieldwork conducted between 2005 and 2009 at a government agency that moved from the capital of Sweden to a smaller town in the north of Sweden. The ethnographic source material was analyzed using discourse analysis. The analysis centres on a discussion of how processes of professional identification became conditioned by social structures in terms of gender, age, and social class in relocation work. I furthermore discuss the ways in which images of geographies and emotions could be regarded as social categories that conditioned professional identities and had implications for how the move of the agency was organized and conducted, for example for the transferring of competency, travelling on business, and setting up new work practices.  The establishment of professional identity positions functioned to stabilize the social environment during the move - a time when many things at work seemed to be in turmoil. At the same time the positions worked to privilege some ways of professional identification and exclude others. Attention should be drawn to the ways in which agency staff became enmeshed in power structures, norms, ideals, images, and plans for the future that limited their actions in various ways. It is therefore important that the features of professional identification in this relocation process should be further discussed, not primarily as individual concerns of particular individuals, or even a particular agency or location, but as a vital issue of the greatest concern to the welfare state. / Decentralization of government agencies, work force mobility and rural development

Mathematical logic and automata theory are two scientific disciplines with a close relationship that is not only fundamental for many theoretical results but also forms the basis of a coherent methodology for the verification and synthesis of computing systems. This connection goes back to a much longer history in the 1960s, through the fundamental work of Büchi-Elgot-Trakhtenbrot, which shows the expressive equivalence of automata and logical systems such as monadic second-order logic on finite and infinite words. This allowed the handling of specifications (where global system properties are stated), and implementations (which involve the definition of the local steps in order to satisfy the global goals laid out in the specifications) in a single framework. This connection has been extended to and well-investigated for many other structures such as trees, finite pictures, timed words and data words. For many computer science applications, however, quantitative phenomena need to be modelled, as well. Examples are vagueness and uncertainty of a statement, length of time periods, spatial information, and resource consumption. Weighted automata, introduced by Schützenberger, are prominent models for quantitative aspects of systems. The framework of weighted monadic second-order logic over words was first introduced by Droste and Gastin. They gave a characterization of quantitative behavior of weighted finite automata, as semantics of monadic second-order sentences within their logic. Meanwhile, the idea of weighted logics was also applied to devices recognizing more general structures such as weighted tree automata, weighted automata on infinite words or traces. The main goal of this thesis is to give logical characterizations for weighted automata models on pictures and data words as well as for Büchi-tiling systems in the spirit of the classical Büchi-Elgot theorem. As the second goal, we deal with synchronizing problem for data words. Below, we briefly summarize the contents of this thesis. Informally, a two-dimensional string is called a picture and is defined as a rectangular array of symbols taken from a finite alphabet. A two-dimensional language (or picture language) is a set of pictures. Picture languages have been intensively investigated by several research groups. In Chapter 1, we define weighted two-dimensional on-line tessellation automata (W2OTA) taking weights from a new weight structure called picture valuation monoid. This new weighted picture automaton model can be used to model several applications, e.g. the average density of a picture. Such aspects could not be modelled by semiring weighted picture automaton model. The behavior of this automaton model is a picture series mapping pictures over an alphabet to elements of a picture valuation monoid. As one of our main results, we prove a Nivat theorem for W2OTA. It shows that recognizable picture series can be obtained precisely as projections of particularly simple unambiguously recognizable series restricted to unambiguous recognizable picture languages. In addition, we introduce a weighted monadic second-order logic (WMSO) which can model average density of pictures. As the other main result, we show that W2OTA and a suitable fragment of our weighted MSO logic are expressively equivalent. In Chapter 2, we generalize the notion of finite pictures to +ω-pictures, i.e., pictures which have finite number of rows and infinite number of columns. We extend conventional tiling systems with a Büchi acceptance condition in order to define the class of Büchi-tiling recognizable +ω-picture languages. The class of recognizable +ω-picture languages is indeed, a natural generalization of ω-regular languages. We show that the class of all Büchi-tiling recognizable +ω-picture languages has the similar closure properties as the class of tiling recognizable languages of finite pictures: it is closed under projection, union, and intersection, but not under complementation. While for languages of finite pictures, tiling recognizability and EMSO-definability coincide, the situation is quite different for languages of +ω-pictures. In this setting, the notion of tiling recognizability does not even cover the language of all +ω -pictures over Σ = {a, b} in which the letter a occurs at least once – a picture language that can easily be defined in first-order logic. As a consequence, EMSO is too strong for being captured by the class of tiling recognizable +ω-picture languages. On the other hand, EMSO is too weak for being captured by the class of all Büchi-tiling recognizable +ω-picture languages. To obtain a logical characterization of this class, we introduce the logic EMSO∞, which extends EMSO with existential quantification of infinite sets. Additionally, using combinatorial arguments, we show that the Büchi characterization theorem for ω-regular languges does not carry over to the Büchi-tiling recognizable +ω-picture languages. In Chapter 3, we consider the connection between weighted register automata and weighted logic on data words. Data words are sequences of pairs where the first element is taken from a finite alphabet (as in classical words) and the second element is taken from an infinite data domain. Register automata, introduced by Francez and Kaminski, provide a widely studied model for reasoning on data words. These automata can be considered as classical nondeterministic finite automata equipped with a finite set of registers which are used to store data in order to compare them with some data in the future. In this chapter, for quantitative reasoning on data words, we introduce weighted register automata over commutative data semirings equipped with a collection of binary data functions in the spirit of the classical theory of weighted automata. Whereas in the models of register automata known from the literature data are usually compared with respect to equality or a linear order, here we allow data comparison by means of an arbitrary collection of binary data relations. This approach permits easily to incorporate timed automata and weighted timed automata into our framework. Motivated by the seminal Büchi-Elgot-Trakhtenbrot theorem about the expressive equivalence of finite automata and monadic second-order (MSO) logic and by the weighted MSO logic of Droste and Gastin, we introduce weighted MSO logic on data words and give a logical characterization of weighted register automata. In Chapter 4, we study the concept of synchronizing data words in register automata. The synchronizing problem for data words asks whether there exists a data word that sends all states of the register automaton to a single state. The class of register automata that we consider here has a decidable non-emptiness problem, and the subclass of nondeterministic register automata with a single register has a decidable non-universality problem. We provide the complexity bounds of the synchronizing problem in the family of deterministic register automata with k registers (k-DRA), and in the family of nondeterministic register automata with single register (1-NRA), and in general undecidability of the problem in the family of k-NRA. To this end, we prove that, for k-DRA, inputting data words with only 2k + 1 distinct data values, from the infinite data domain, is sufficient to synchronize. Then, we show that the synchronizing problem for k-DRA is in general PSPACE-complete, and it is in NLOGSPACE for 1-DRA. For nondeterministic register automata (NRA), we show that Ackermann(n) distinct data, where n is the number of states of the register automaton, might be necessary to synchronize. Then, by means of a construction, proving that the synchronizing problem and the non-universality problem in 1-NRA are interreducible, we show the Ackermann-completeness of the problem for 1-NRA. However, for k-NRA, in general, we prove that this problem is undecidable due to the unbounded length of synchronizing data words.

Providing a logical characterisation of rational agent reasoning has been a long standing challenge in artificial intelligence (AI) research. It is a challenge that is not only of interest for the construction of AI agents, but is of equal importance in the modelling of agent behaviour. The goal of this thesis is to contribute to the formalisation of agent reasoning by showing that the computational limitations of agents is a vital component of modelling rational behaviour. To achieve this aim, both motivational and formal aspects of resource-bounded agents are examined. It is a central argument of this thesis that accounting for computational limitations is critical to the success of agent reasoning, yet has received only limited attention from the broader research community. Consequently, an important contribution of this thesis is in its advancing of motivational arguments in support of the need to account for computational limitations in agent reasoning research. As a natural progression from the motivational arguments, the majority of this thesis is devoted to an examination of propositional approximate logics. These logics represent a step towards the development of resource-bounded agents, but are also applicable to other areas of automated reasoning. This thesis makes a number of contributions in mapping the space of approximate logics. In particular, it draws a connection between approximate logics and knowledge compilation, by developing an approximate knowledge compilation method based on Cadoli and Schaerf??s S-3 family of approximate logics. This method allows for the incremental compilation of a knowledge base, thus reducing the need for a costly recompilation process. Furthermore, each approximate compilation has well-defined logical properties due to its correspondence to a particular S-3 logic. Important contributions are also made in the examination of approximate logics for clausal reasoning. Clausal reasoning is of particular interest due to the efficiency of modern clausal satisfiability solvers and the related research into problem hardness. In particular, Finger's Logics of Limited Bivalence are shown to be applicable to clausal reasoning. This is subsequently shown to logically characterise the behaviour of the well-known DPLL algorithm for determining boolean satisfiability, when subjected to restricted branching.

We outline a novel technique that maps the satisfiability problems of second-order logics, in particular WSnS (weak monadic second-order logic with n successors), S1S (monadic second-order logic with one successor), and of μ-calculus, to the problem of query evaluation of Complex-value Datalog queries. In this dissertation, we propose techniques that use database evaluation and optimization techniques for automata-based decision procedures for the above logics. We show how the use of advanced implementation techniques for Deductive databases and for Logic Programs, in particular the use of tabling, yields a considerable improvement in performance over more traditional approaches. We also explore various optimizations of the proposed technique, in particular we consider variants of tabling and goal reordering. We then show that the decision problem for S1S can be mapped to the problem of query evaluation of Complex-value Datalog queries. We explore optimizations that can be applied to various types of formulas. Last, we propose analogous techniques that allow us to approach μ-calculus satisfiability problem in an incremental fashion and without the need for re-computation. In addition, we outline a top-down evaluation technique to drive our incremental procedure and propose heuristics that guide the problem partitioning to reduce the size of the problems that need to be solved.

We outline a novel technique that maps the satisfiability problems of second-order logics, in particular WSnS (weak monadic second-order logic with n successors), S1S (monadic second-order logic with one successor), and of μ-calculus, to the problem of query evaluation of Complex-value Datalog queries. In this dissertation, we propose techniques that use database evaluation and optimization techniques for automata-based decision procedures for the above logics. We show how the use of advanced implementation techniques for Deductive databases and for Logic Programs, in particular the use of tabling, yields a considerable improvement in performance over more traditional approaches. We also explore various optimizations of the proposed technique, in particular we consider variants of tabling and goal reordering. We then show that the decision problem for S1S can be mapped to the problem of query evaluation of Complex-value Datalog queries. We explore optimizations that can be applied to various types of formulas. Last, we propose analogous techniques that allow us to approach μ-calculus satisfiability problem in an incremental fashion and without the need for re-computation. In addition, we outline a top-down evaluation technique to drive our incremental procedure and propose heuristics that guide the problem partitioning to reduce the size of the problems that need to be solved.

Ο Παγκόσμιος Ιστός έχει αλλάξει τον τρόπο που οι άνθρωποι επικοινωνούν μεταξύ τους καθώς και τον τρόπο με τον οποίο οι επιχειρήσεις διευθύνονται. Ως επέκταση του παγκόσμιου ιστού εμφανίζεται ο Σημασιολογικός Ιστός. Ο Σημασιολογικός Ιστός είναι ειδικότερα, ένας Ιστός από πληροφορίες που είναι δυνατό να διαβαστούν από τις μηχανές και η έννοια των οποίων είναι σαφώς καθορισμένη από πρότυπα. Στόχος της διπλωματική αυτής είναι η επέκταση και η εμβάθυνση σε θεμελιώδεις έννοιες του Σημασιολογικού Ιστού και η σύνδεση του με τις ΤΠΕ στην εκπαίδευση. Στα παρακάτω κεφάλαια προσεγγίζεται αναλυτικά η έννοια του Σημασιολογικού Ιστού, καθώς επίσης και οι βασικές γλώσσες σήμανσης του οι οποίες είναι: 1. Η γλώσσα σήμανσης XML, μια γλώσσα που επιτρέπει τη γραφή δομημένων εγγράφων ιστού με ένα καθορισμένο από το χρήστη λεξιλόγιο. 2. Tο Resource Description Framework (RDF) που είναι ένα πλαίσιο για την αντιπροσώπευση των πληροφοριών στον Παγκόσμιο Ιστό, όπου αναλύονται οι βασικές έννοιες που χρησιμοποιεί όπως το γραφικό μοντέλο δεδομένων, λεξιλόγιο βασισμένο στο URI, τύποι δεδομένων κ.α. 3. Το λεξιλόγιο καθορισμού του RDF (RDF Schema), που καθορίζει τις κλάσεις και τις ιδιότητες που μπορούν να χρησιμοποιηθούν για να περιγράψουν κλάσεις, ιδιότητες και άλλες πηγές. Σε επόμενο κεφάλαιο εισάγουμε στον αναγνώστη τον όρο της οντολογίας. Αναλύουμε το τι είναι οντολογία, τις κύριες λειτουργίες των οντολογιών, και προτείνεται ένα περίγραμμα για την κατασκευή των οντολογιών. Ξεχωριστή αναφορά γίνεται στο Ontology Inference Layer OIL που είναι μια πρόταση για ένα βασισμένο στον Ιστό στρώμα αντιπροσώπευσης και συμπεράσματος των οντολογιών. Επίσης γίνεται αναφορά στη βασική ιδέα σχεδιασμού του OIL που είναι το onion model του. Ακολούθως, αναλύουμε τον τρόπο με τον οποίο συντάσσεται μια οντολογία στη γλώσσα OIL. Ως συνέχεια του παραπάνω εμφανίζεται η DAML+OIL, που είναι μια σημασιολογική γλώσσα για τις πηγές του Ιστού. Στηρίζεται στα πρότυπα του W3C όπως το RDF και το RDF Schema, και επεκτείνει αυτές τις γλώσσες με ακόμα πιο πλούσιες αρχές διαμόρφωσης. Στη συνέχεια προσεγγίζουμε εκτενώς την Web Ontology Language OWL που είναι μια σημασιολογική γλώσσα σήμανσης για την έκδοση και τη διανομή των οντολογιών στον Παγκόσμιο Ιστό. Η σύνδεση του σημασιολογικού ιστού με την εκπαίδευση είναι το θέμα που αναλύεται παρακάτω με τίτλο Εκπαιδευτικός Σημασιολογικός Ιστός και γίνεται εκτενής αναφορά στις προκλήσεις και τις προοπτικές που διαφαίνονται. Η σύνδεση αυτή γίνεται με το προσαρμοστικό WBES. Ακόμα, εξετάζουμε μερικά σενάρια εφαρμογής του εκπαιδευτικού Σημασιολογικού Ιστού όπως την βασισμένη στη σημασιολογία αναζήτηση για εκπαιδευτικό περιεχόμενο, την περιήγηση στη γνώση ή «προσωπικές πύλες», τα βασισμένα στη σημασιολογία μαθήματα και τις εκπαιδευτικές υπηρεσίες σημασιολογικού ιστού. Τέλος, αναφέρουμε με συντομία εφαρμογές εκπαίδευσης βασισμένες σε οντολογίες όπως το πρόγραμμα CIPHER, το πρόγραμμα Connexions κ.α. / -

Providing a logical characterisation of rational agent reasoning has been a long standing challenge in artificial intelligence (AI) research. It is a challenge that is not only of interest for the construction of AI agents, but is of equal importance in the modelling of agent behaviour. The goal of this thesis is to contribute to the formalisation of agent reasoning by showing that the computational limitations of agents is a vital component of modelling rational behaviour. To achieve this aim, both motivational and formal aspects of resource-bounded agents are examined. It is a central argument of this thesis that accounting for computational limitations is critical to the success of agent reasoning, yet has received only limited attention from the broader research community. Consequently, an important contribution of this thesis is in its advancing of motivational arguments in support of the need to account for computational limitations in agent reasoning research. As a natural progression from the motivational arguments, the majority of this thesis is devoted to an examination of propositional approximate logics. These logics represent a step towards the development of resource-bounded agents, but are also applicable to other areas of automated reasoning. This thesis makes a number of contributions in mapping the space of approximate logics. In particular, it draws a connection between approximate logics and knowledge compilation, by developing an approximate knowledge compilation method based on Cadoli and Schaerf??s S-3 family of approximate logics. This method allows for the incremental compilation of a knowledge base, thus reducing the need for a costly recompilation process. Furthermore, each approximate compilation has well-defined logical properties due to its correspondence to a particular S-3 logic. Important contributions are also made in the examination of approximate logics for clausal reasoning. Clausal reasoning is of particular interest due to the efficiency of modern clausal satisfiability solvers and the related research into problem hardness. In particular, Finger's Logics of Limited Bivalence are shown to be applicable to clausal reasoning. This is subsequently shown to logically characterise the behaviour of the well-known DPLL algorithm for determining boolean satisfiability, when subjected to restricted branching.

Thesis (Ph. D.)--Mechanical Engineering, Georgia Institute of Technology, 2007. / Nelson Baker, Committee Member ; Charles Eastman, Committee Member ; Christiaan Paredis, Committee Member ; Janet Allen, Committee Member ; David Rosen, Committee Chair.