The eight topological RCC8(or Egenhofer-Franzosa)- relations between spatial regions play a fundamental role in spatial reasoning, spatial and constraint databases, and geographical information systems. In analogy with Halpern and Shoham’s modal logic of time intervals based on the Allen relations, we introduce a family of modal logics equipped with eight modal operators that are interpreted by the RCC8-relations. The semantics is based on region spaces induced by standard topological spaces, in particular the real plane. We investigate the expressive power and computational complexity of the logics obtained in this way. It turns our that, similar to Halpern and Shoham’s logic, the expressive power is rather natural, but the computational behavior is problematic: topological modal logics are usually undecidable and often not even recursively enumerable. This even holds if we restrict ourselves to classes of finite region spaces or to substructures of region spaces induced by topological spaces. We also analyze modal logics based on the set of RCC5relations, with similar results.

We make a first step towards adapting an existing approach for privacypreserving publishing of linked data to Description Logic (DL) ontologies. We consider the case where both the knowledge about individuals and the privacy policies are expressed using concepts of the DL EL, which corresponds to the setting where the ontology is an EL instance store. We introduce the notions of compliance of a concept with a policy and of safety of a concept for a policy, and show how optimal compliant (safe) generalizations of a given EL concept can be computed. In addition, we investigate the complexity of the optimality problem.

In contrast to qualitative linear temporal logics, which can be used to state that some property will eventually be satisfied, metric temporal logics allow to formulate constraints on how long it may take until the property is satisfied. While most of the work on combining Description Logics (DLs) with temporal logics has concentrated on qualitative temporal logics, there has recently been a growing interest in extending this work to the quantitative case. In this paper, we complement existing results on the combination of DLs with metric temporal logics over the natural numbers by introducing interval-rigid names. This allows to state that elements in the extension of certain names stay in this extension for at least some specified amount of time.

Although being quite inexpressive, the description logic (DL) FL₀, which provides only conjunction, value restriction and the top concept as concept constructors, has an intractable subsumption problem in the presence of terminologies (TBoxes): subsumption reasoning w.r.t. acyclic FL₀ TBoxes is coNP-complete, and becomes even ExpTime-complete in case general TBoxes are used. In the present paper, we use automata working on infinite trees to solve both standard and non-standard inferences in FL₀ w.r.t. general TBoxes. First, we give an alternative proof of the ExpTime upper bound for subsumption in FL₀ w.r.t. general TBoxes based on the use of looping tree automata. Second, we employ parity tree automata to tackle non-standard inference problems such as computing the least common subsumer and the difference of FL₀ concepts w.r.t. general TBoxes.

Fuzzy Description Logics (FDLs) combine classical Description Logics with the semantics of Fuzzy Logics in order to represent and reason with vague knowledge. Most FDLs using truth values from the interval [0; 1] have been shown to be undecidable in the presence of a negation constructor and general concept inclusions. One exception are those FDLs whose semantics is based on the infinitely valued Gödel t-norm (G). We extend previous decidability results for the FDL G-ALC to deal with complex role inclusions, nominals, inverse roles, and qualified number restrictions. Our novel approach is based on a combination of the known crispification technique for finitely valued FDLs and an automata-based procedure for reasoning in G-ALC.

We present an extensions of our previous work on axiomatizing confident general concept inclusions in given finite interpretations. Within this extension we allow external experts to interactively provide counterexamples to general concept inclusions with otherwise enough confidence in the given data. This extensions allows us to distinguish between erroneous counterexamples in the data and rare, but valid counterexamples.

Matching concept descriptions against concept patterns was introduced as a new inference task in Description Logics (DLs) almost 20 years ago, motivated by applications in the Classic system. For the DL EL, it was shown in 2000 that the matching problem is NP-complete. It then took almost 10 years before this NP-completeness result could be extended from matching to unification in EL. The next big challenge was then to further extend these results from matching and unification without a TBox to matching and unification w.r.t. a general TBox, i.e., a finite set of general concept inclusions. For unification, we could show some partial results for general TBoxes that satisfy a certain restriction on cyclic dependencies between concepts, but the general case is still open. For matching, we solve the general case in this paper: we show that matching in EL w.r.t. general TBoxes is NP-complete by introducing a goal-oriented matching algorithm that uses non-deterministic rules to transform a given matching problem into a solved form by a polynomial number of rule applications. We also investigate some tractable variants of the matching problem.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / A very important aspect in robotics is the decision making and execution the system uses to achieve its goals. In literature, many different approaches can be found about how the robot must behave in different situations in order to have a more robust system. Subsumption architecture is one of the most used and referenced in the area. In this architecture, the global task is divided into subtasks which are performed by behaviors organized in hierarchical layers. However, little research has been done regarding the stability analysis of this architecture. Behavioral changes imply in controller switching, which can lead the system to instability even in cases where all controllers are stable. In this work, a subsumption architecture with guaranteed stability is presented based on the theory of switched systems with main control objective. In addition, a formalism capable of allowing behaviors modeling in a simple and fast way is proposed based on the theory of discrete events systems. Tests in real environments were performed with the Pioneer P3-DX robot and obtained results demonstrate the proposed approach effectiveness. / Um aspecto muito importante na robótica é a tomada de decisão e execução que o sistema utiliza para alcançar seus objetivos. Na literatura, existem vários trabalhos diferentes para abordar como o robô deve se comportar diante de várias situações diferentes a fim de trazer uma maior robustez ao sistema, sendo a arquitetura de subsunção uma das mais utilizadas e referenciadas na área. Nesta arquitetura, a tarefa global é dividida em subtarefas que são executadas por comportamentos organizados em camadas de forma hierárquica. No entanto, pouco se pesquisa no que diz respeito a análise de estabilidade desta arquitetura, sendo que as mudanças de comportamento implicam em chaveamento de controladores, que por sua vez podem levar o sistema a instabilidade mesmo em casos em que todos os controladores sejam estáveis. Desta forma, neste trabalho é apresentada uma arquitetura de subsunção com prova de estabilidade garantida com base na teoria de controle chaveado com objetivo de controle principal. Além disso, um formalismo capaz de permitir a modelagem dos comportamentos de forma simples e rápida é proposto com base na teoria de sistemas a eventos discretos. Testes em ambientes reais foram realizados com o robô Pioneer P3-DX e os resultados obtidos comprovam a eficácia da abordagem proposta.

FundaÃÃo de Amparo à Pesquisa do Estado do Cearà / A presente Tese compreende um exame crÃtico da estrutura de funcionamento do sistema do capital, à luz da contradiÃÃo central assinalada por Karl Marx nos Grundrisse. A contradiÃÃo vai se tornando visÃvel com a substituiÃÃo do trabalho vivo (trabalho humano direto) pelo trabalho morto (mÃquinas). Em decorrÃncia, esvazia-se a substÃncia do valor e os trabalhadores diretos sÃo reduzidos à condiÃÃo de apÃndice de mÃquinas que trabalham, restando-lhes as atividades de reguladores e de suportes para complexos automÃticos. O movimento lÃgico do valor e o transcurso histÃrico do processo de subsunÃÃo do trabalho ao capital, propiciam a hipÃtese de que o conjunto dos trabalhadores estaria sendo submetido a uma tendÃncia perversa que qualifica desqualificando suas aptidÃes e habilidades. Ao mesmo tempo, simplifica o trabalho e desvaloriza a forÃa-de-trabalho. A fim de averiguar tal processo de disrupÃÃo do mundo do trabalho, constituiu-se um objeto de pesquisa que permitisse checar a atuaÃÃo de trabalhadores tidos, pelo senso comum, como altamente qualificados. Eis a razÃo pela qual se tomou como plano investigativo, a âbusca dos egressos do CEFETCEâ no mercado de trabalho, centrando a investigaÃÃo nos haveres tecnolÃgicos de mecatrÃnicos e telemÃticos. A questÃo bÃsica à verificar atà que ponto esses operadores high-tech ativam a gama dos conhecimentos obtidos em sua formaÃÃo teÃrico-prÃtica cefeteana, no dia-a-dia das atividades profissionais. Foram entrevistados sessenta tecnÃlogos, alÃm de professores, administradores industriÃrios e operÃrios de fÃbrica vinculados a dÃspares ramos de produÃÃo de mercadorias. As entrevistas foram sempre secundadas por visitas a vÃrias plantas produtivas. Como resultado, o pesquisador foi premiado com um fÃrtil material sociolÃgico, prenhe de expressÃes simbÃlicas e de constructos tÃcnicos. A materialidade e a imaterialidade das experiÃncias, explÃcita e implicitamente vivenciadas, evidenciaram a âcontradiÃÃo em processoâ no coraÃÃo de sistemas de produÃÃo automÃticos. Nestes, estÃo reservados para os trabalhadores imediatos atos fetichistas como âcuidarâ (de mÃquinas), âassistirâ (linhas de produÃÃo), âolharâ (supervisÃrios) e âtrocar placasâ (eletrÃnicas) etc. / The present Thesis comprises a critical examination of the structure of the working of the system of the capital, in the light of the central contradiction indicated by Karl Marx in the Grundrisse. The expression of the contradiction gets visibility with the substitution for dead labor (machines) of live labor (human direct labor). Therefore, the substance of value becomes empty and the direct laborers are reduced to the condition of appendix of machines they work with, remaining to them the activities of regulating and supporting the automatic complexes. The logical movement of value and the historical course of the process of subsumption of labor to capital provide the hypothesis that the working class were being submitted to a perverse trend that qualifies in a disqualifying manner its aptitudes and abilities. At the same time, that process simplifies the labor and devaluates labor-force. In order to investigate such process of disruption of the world of labor it was crucial to choose an object of research that allowed checking the performance of workers recognized by common sense as highly qualified. That is the reason for which the âsearch of the egresses of the CEFETCEâ in the labor market was the core of the investigation. Technological assets of mechathronics and telematics technicians were investigate. The basic question of the inquiry is to verify to what extent these high-tech operators activate, the gamma of knowledge acquired during theoretical and practical formation at CEFETCE, to their everyday professional activities. Sixty technologists were interviewed, as well as, professors, industrial managers and laborers of various branches of merchandise production. The interviews always were seconded by visits to some productive plants. As a result, the researcher was awarded with a fertile sociological material, pregnant of symbolic expressions and technological constructs. The materiality and the immateriality of the experiences evidenced âthe contradiction in processâ in the heart of automatic systems of production. In those systems, fetishist production acts are set aside for the direct workers, in the form âcaring ofâ (machines), âwatchingâ (production lines), âlooking atâ (monitors) and âchanging platesâ (electronics) etc.

Simple counting quantifiers that can be used to compare the number of role successors of an individual or the cardinality of a concept with a fixed natural number have been employed in Description Logics (DLs) for more than two decades under the respective names of number restrictions and cardinality restrictions on concepts. Recently, we have considerably extended the expressivity of such quantifiers by allowing to impose set and cardinality constraints formulated in the quantifier-free fragment of Boolean Algebra with Presburger Arithmetic (QFBAPA) on sets of role successors and concepts, respectively. We were able to prove that this extension does not increase the complexity of reasoning. In the present paper, we investigate the expressive power of the DLs obtained in this way, using appropriate bisimulation characterizations and 0–1 laws as tools to differentiate between the expressiveness of different logics. In particular, we show that, in contrast to most classical DLs, these logics are no longer expressible in first-order predicate logic (FOL), and we characterize their first-order fragments. In most of our previous work on DLs with QFBAPA-based set and cardinality constraints we have employed finiteness restrictions on interpretations to ensure that the obtained sets are finite, as required by the standard semantics for QFBAPA. Here we dispense with these restrictions to ease the comparison with classical DLs, where one usually considers arbitrary models rather than finite ones, easier. It turns out that doing so does not change the complexity of reasoning.