Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Dies ist eine Eigenschaft des Typs Text.

Seiten mit dem Attribut „Abstract“

Es werden 25 Seiten angezeigt, die dieses Attribut verwenden:

(vorherige 25) (nächste 25)


Article1226 +Durch den Einsatz von numerischen Modellen für ingenieurtechnische Problemstellungen, wie z. B. der FEM oder der FDM, können zunehmend komplexere Berechnungen in immer kürzerer Zeit bewältigt werden. Gleichzeitig ergibt sich jedoch bei dem Einsatz dieser Werkzeuge der Bedarf an Werten für die verschiedenen Modellparameter, von rein konstitutiven Kennwerten bis hin zu geometrischen Angaben, für deren Bestimmung zunehmend inverse Verfahren Anwendung finden. Bei der Nutzung dieser Methoden ist jedoch - insbesondere bei komplizierten Simulationen - mit sehr langen Berechnungszeiten zu rechnen. Gegenstand dieses Beitrags ist die Vorstellung einer Verfahrensklasse, die eine Abschätzung der Lösung solcher inverser Aufgaben auf der Basis von relativ wenigen Stützstellen ermöglicht. An die Verteilung der Stützstellen werden geringste Anforderungen gestellt, so daß diese wahlweise aus vorhergehenden Simulationen oder auch aus alternativen Quellen stammen können. Im Rahmen dieses Beitrags soll ausgehend von einer Einführung in den theoretischen Ansatz eine Strategie zur Beschleunigung der Lösung von inversen Problemstellungen und Optimierungsaufgaben an einem Beispiel aus dem Gebiet der Geomechanik vorgestellt werden.  +
Article1303 +Domains and metric spaces are two central tools for the study of denotational semantics in computer science, but are otherwise very different in many fundamental aspects. A construction that tries to establish links between both paradigms is the space of formal balls, a continuous poset which can be defined for every metric space and that reflects many of its properties. On the other hand, in order to obtain a broader framework for applications and possible connections to domain theory, generalized ultrametric spaces (gums) have been introduced. In this paper, we employ the space of formal balls as a tool for studying these more general metrics by using concepts and results from domain theory. It turns out that many properties of the metric can be characterized via its formal-ball space. Furthermore, we can state new results on the topology of gums as well as two new fixed point theorems, which may be compared to the Prieß-Crampe and Ribenboim theorem, and the Banach fixed point theorem, respectively. Deeper insights into the nature of formal-ball spaces are gained by applying methods from category theory. Our results suggest that, while being a useful tool for the study of gums, the space of formal balls does not provide the hoped-for general connection to domain theory.  +
Article1551 +Wikipedia is the world's largest collaboratively edited source of encyclopaedic knowledge. But in spite of its utility, its content is barely machine-interpretable and only weakly structured. With Semantic MediaWiki we provide an extension that enables wiki-users to semantically annotate wiki pages, based on which the wiki contents can be browsed, searched, and reused in novel ways. In this paper, we give an extended overview of Semantic MediaWiki and discuss experiences regarding performance and current applications.  +
Article1649 +A common perception is that there are two competing visions for the future evolution of the Web: the Semantic Web and Web 2.0. A closer look, though, reveals that the core technologies and concerns of these two approaches are complementary and that each field can and must draw from the other's strengths. We believe that future Web applications will retain the Web 2.0 focus on community and usability, while drawing on Semantic Web infrastructure to facilitate mashup-like information sharing. However, there are several open issues that must be addressed before such applications can become commonplace. In this paper, we outline a semantic weblogs scenario that illustrates the potential for combining Web 2.0 and Semantic Web technologies, while highlighting the unresolved issues that impede its realization. Nevertheless, we believe that the scenario can be realized in the short-term. We point to recent progress made in resolving each of the issues as well as future research directions for each of the communities.  +
Article1983 +Research on natural language interfaces has mainly concentrated on question interpretation as well as answer computation, but not focused as much on answer presentation. In most natural language interfaces, answers are in fact provided extensionally as a list of all those instances satisfying the query description. In this paper, we aim to go beyond such a mere listing of facts and move towards producing additional descriptions of the query results referred to as 'intensional answers'. We define an intensional answer (IA) as a logical description of the actual set of answer items to a given query in terms of properties that are shared by exactly these answer items. We argue that IAs can enhance a user's understanding of the answer itself but also of the underlying knowledge base. In particular, we present an approach for computing an intensional answer given an extensional answer (i.e. a set of entities) returned as a result of a question. In our approach, an intensional answer is represented by a clause and computed based on Inductive Logic Programming (ILP) techniques, in particular bottom-up clause generalization. The approach is evaluated in terms of usefulness and time performance, and we discuss its potential for helping to detect flaws in the knowledge base as well as to interactively enrich it with new knowledge. While the approach is used in the context of a natural language question answering system in our settings, it clearly has applications beyond, e.g. in the context of research on generating referring expressions.  +
Article1984 +When working with numerical models, it is essential to determine model parameters which are as realistic as possible. Optimization techniques are being employed more and more frequently for solving this task. However, using these methods may lead to very high time costs - in particular, if rather complicated forward calculations are involved. In this paper, we present a class of methods that allows estimating the solution of this kind of optimization problems based on relatively few sampling points. We put very weak constraints on the sampling point distribution; hence, they may be taken from previous forward calculations as well as from alternative sources.Starting from an introduction into the theoretical approach, a strategy for speeding up inverse optimization problems is introduced which is illustrated by an example from geomechanics.  +
Article3000 +Supervisory control of distributed DES with a global specification and local supervisors is a difficult problem. For global specifications, the equivalent conditions for local control synthesis to equal global control synthesis may not be met. This paper formulates and solves a control synthesis problem for a generator with a global specification and with a combination of a coordinator and local controllers. Conditional controllability is proven to be an equivalent condition for the existence of such a coordinated controller. A procedure to compute the least restrictive solution within our coordination control architecture is provided and conditions under which the result coincides with the supremal controllable sublanguage are stated.  +
Article3001 +Recently, an infinite hierarchy of languages accepted by stateless deterministic pushdown automata has been established based on the number of pushdown symbols. However, the witness language for the nth level of the hierarchy is over an input alphabet with 2(n − 1) elements. In this paper, we improve this result by showing that a binary alphabet is sufficient to establish this hierarchy. As a consequence of our construction, we solve the open problem formulated by Meduna et al. Then we extend these results to m-state realtime deterministic pushdown automata, for all m ≥ 1. The existence of such a hierarchy for m-state deterministic pushdown automata is left open.  +
Article3002 +In this paper, we prove that the most important concept of supervisory control of discrete-event systems, the controllability property, is undecidable for two deterministic context-free languages K and L, where L is prefix closed, even though K is a subset of L. If K is not a subset of L, the undecidability follows from the work by Sreenivas. However, the case where K is a subset of L does not follow from that work because it is decidable whether K and L are equivalent as shown by Sénizergues. Thus, our result completes this study. The problem is also mentioned as open in the Ph.D. thesis by Griffin, who extended the supervisory control framework so that the specification language is modeled as a deterministic context-free language (compared to the classical approach where the specification is regular) and the plant language is regular. This approach is of interest because it brings an opportunity for more concise representations of the specification (as discussed, e.g., in the work by Geffert et al.) and, therefore, in some sense it treats the most interesting problem of current supervisory control theory, the state-space explosion problem.  +
Article3003 +Context-free grammars are widely used for the simple form of their rules. A derivation step consists of the choice of a nonterminal of the sentential form and of an application of a rule rewriting it. Several regulations of the derivation process have been studied to increase the power of context-free grammars. In the resulting grammars, however, not only the symbols to be rewritten are restricted, but also the rules to be applied. In this paper, we study context-free grammars with a simpler restriction where only symbols to be rewritten are restricted, not the rules, in the sense that any rule rewriting the chosen nonterminal can be applied. We prove that these grammars have the same power as random context, matrix, or programmed grammars. We also present two improved normal forms and discuss the characterization of context-sensitive languages by a variant using strings of length at most two instead of symbols.  +
Article3004 +The requirement of a language to be conditionally decomposable is imposed on a specification language in the coordination supervisory control framework of discrete-event systems. In this paper, we present a polynomial-time algorithm for verification whether a language is conditionally decomposable with respect to given alphabets. Moreover, we also present a polynomial-time algorithm to extend the common alphabet so that the language becomes conditionally decomposable. A relationship of conditional decomposability to nonblockingness of modular discrete-event systems in general settings is also discussed in this paper. It is shown that conditional decomposability is a weaker condition than nonblockingness.  +
Article3005 +A transition is unobservable if it is labeled by a symbol removed by a projection. The present paper investigates a new structural property of incomplete deterministic finite automata–a number of states incident with an unobservable transition–and its effect on the state complexity of projected regular languages. We show that the known upper bound can be met only by automata with one unobservable transition (up to unobservable multi-transitions). We improve this upper bound by taking into consideration the structural property of minimal incomplete automata, and prove the tightness of new upper bounds. Special attention is focused on the case of finite languages. The paper also presents and discusses several fundamental problems which are still open.  +
Article3006 +In this paper, we revise and further investigate the coordination control approach proposed for supervisory control of distributed discrete-event systems with synchronous communication based on the Ramadge-Wonham automata framework. The notions of conditional decomposability, conditional controllability, and conditional closedness ensuring the existence of a solution are carefully revised and simplified. The approach is generalized to non-prefix-closed languages, that is, supremal conditionally controllable sublanguages of not necessary prefix-closed languages are discussed. Non-prefix-closed languages introduce the blocking issue into coordination control, hence a procedure to compute a coordinator for nonblockingness is included. The optimization problem concerning the size of a coordinator is under investigation. We prove that to find the minimal extension of the coordinator event set for which a given specification language is conditionally decomposable is NP-hard. In other words, unless P=NP, it is not possible to find a polynomial algorithm to compute the minimal coordinator with respect to the number of events.  +
Article3007 +Recently, stage and cf2 semantics for abstract argumentation attracted specific attention. By distancing from the notion of defence, they are capable to select arguments out of odd-length cycles. In case of cf2 semantics, the SCC-recursive schema guarantees that important evaluation criteria for argumentation semantics, like directionality, weak- and CF-reinstatement, are fulfilled. Beside several desirable properties, both stage and cf2 semantics still have some drawbacks. The stage semantics does not satisfy the above mentioned evaluation criteria, whereas cf2 semantics produces some questionable results on frameworks with cycles of length ≥ 6. Therefore, we suggest to combine stage semantics with the SCC-recursive schema of cf2 semantics. The resulting stage2 semantics overcomes the problems regarding cf2 and stage semantics. We study properties of stage2 semantics and its relations to existing semantics, show that it fulfills the mentioned evaluation criteria, study strong equivalence for stage2 semantics and provide a comprehensive complexity analysis of the associated reasoning problems. Besides the analysis of stage2 semantics, we also complement existing complexity results for cf2 by an analysis of tractable fragments and fixed parameter tractability. Furthermore, we provide answer-set programming (ASP) encodings for stage2 semantics and labelling-based algorithms for cf2 and stage2 semantics.  +
Article3008 +Within the last decade, abstract argumentation has emerged as a central field in Artificial Intelligence. Besides providing a core formalism for many advanced argumentation systems, abstract argumentation has also served to capture several non-monotonic logics and other AI related principles. Although the idea of abstract argumentation is appealingly simple, several reasoning problems in this formalism exhibit high computational complexity. This calls for advanced techniques when it comes to implementation issues, a challenge which has been recently faced from different angles. In this survey, we give an overview on different methods for solving reasoning problems in abstract argumentation and compare their particular features. Moreover, we highlight available state-of-the-art systems for abstract argumentation, which put these methods to practice.  +
Article3009 +OWL 2 EL is a popular ontology language that supports role inclusions---that is, axioms that capture compositional properties of roles. Role inclusions closely correspond to context-free grammars, which was used to show that answering conjunctive queries (CQs) over OWL 2 EL knowledge bases with unrestricted role inclusions is undecidable. However, OWL 2 EL inherits from OWL 2 DL the syntactic regularity restriction on role inclusions, which ensures that role chains implying a particular role can be described using a finite automaton (FA). This is sufficient to ensure decidability of CQ answering; however, the FAs can be worst-case exponential in size so the known approaches do not provide a tight upper complexity bound. In this paper, we solve this open problem and show that answering CQs over OWL 2 EL knowledge bases is PSPACE-complete in combined complexity (i.e., the complexity measured in the total size of the input). To this end, we use a novel encoding of regular role inclusions using bounded-stack pushdown automata---that is, FAs extended with a stack of bounded size. Apart from theoretical interest, our encoding can be used in practical tableau algorithms to avoid the exponential blowup due to role inclusions. In addition, we sharpen the lower complexity bound and show that the problem is PSPACE-hard even if we consider only role inclusions as part of the input (i.e., the query and all other parts of the knowledge base are fixed). Finally, we turn our attention to navigational queries over OWL 2 EL knowledge bases, and we show that answering positive, converse-free conjunctive graph XPath queries is PSPACE-complete as well; this is interesting since allowing the converse operator in queries is known to make the problem EXPTIME-hard. Thus, in this paper we present several important contributions to the landscape of the complexity of answering expressive queries over description logic knowledge bases.  +
Article3010 +Translations to (first-order) Datalog have been used in a number of inferencing techniques for description logics (DLs), yet the relationship between the semantic expressivities of function-free Horn logic and DL is understood only poorly. Although Description Logic Programs (DLP) have been described as DLs in the "expressive intersection" of DL and Datalog, it is unclear what an intersection of two syntactically incomparable logics is, even if both have a first-order logic semantics. In this work, we offer a characterisation for DL fragments that can be expressed, in a concrete sense, in Datalog. We then determine the largest such fragment for the DL ALC, and provide an outlook on the extension of our methods to more expressive DLs.  +
Article3011 +Inprocessing is to apply clause simplification techniques during search and is a very attractive idea since it allows to apply computationally expensive techniques. In this paper we present the search space decomposition formalism SSD that models parallel SAT solvers with clause sharing and inprocessing. The main result of this paper is that the sharing model SSD is sound. In the formalism, we combine clause addition and clause elimination techniques, and it covers many SAT solvers such as PaSAT, PaMira, PMSat, MiraXT and ccc. Inprocessing is not used in these solvers, and we therefore propose a novel way how to combine clause sharing, search space decomposition and inprocessing.  +
Article3012 +Automata-based methods have been successfully employed to prove tight complexity bounds for reasoning in many classical logics, and in particular in Description Logics (DLs). Very recently, the ideas behind these automata-based approaches were adapted for reasoning also in fuzzy extensions of DLs, with semantics based either on finitely many truth degrees or the Gödel t-norm over the interval [0,1]. Clearly, due to the different semantics in these logics, the construction of the automata for fuzzy DLs is more involved than for the classical case. In this paper we provide an overview of the existing automata-based methods for reasoning in fuzzy DLs, with a special emphasis on explaining the ideas and the requirements behind them. The methods vary from deciding emptiness of automata on infinite trees to inclusions between automata on finite words. Overall, we provide a comprehensive perspective on the automata-based methods currently in use, and the many complexity results obtained through them.  +
Article3013 +We give an overview of design and results of the Second International Competition on Computational Models of Argumentation (ICCMA’17). Following the first edition in 2015, the competition evaluates the performance of submitted solvers on computational problems within abstract argumentation. In addition to the four original semantics, ICCMA’2017 includes three additional prominent semantics. Moreover, a dedicated call for benchmarks allowed for introducing a sophisticated instance selection process.  +
Article3014 +The design of efficient solutions for abstract argumentation problems is a crucial step towards advanced argumentation systems. One of the most prominent approaches in the literature is to use Answer-Set Programming (ASP) for this endeavor. In this paper, we present new encodings for three prominent argumentation semantics using the concept of conditional literals in disjunctions as provided by the ASP-system clingo. Our new encodings are not only more succinct than previous versions, but also outperform them on standard benchmarks.  +
Article3016 +Outer joins are ubiquitous in many workloads and Big Data systems. The question of how to best execute outer joins in large parallel systems is particularly challenging, as real world datasets are characterized by data skew leading to performance issues. Although skew handling techniques have been extensively studied for inner joins, there is little published work solving the corresponding problem for parallel outer joins, especially in the extremely popular Cloud computing environment. Conventional approaches to the problem such as ones based on hash redistribution often lead to load balancing problems while duplication-based approaches incur significant overhead in terms of network communication. In this paper, we propose a new approach for efficient skew handling in outer joins over a Cloud computing environment. We present an efficient implementation of our approach over the Spark framework. We evaluate the performance of our approach on a 192-core system with large test datasets in excess of 100GB and with varying skew. Experimental results show that our approach is scalable and, at least of in cases of high skew, significantly faster than the state-of-the-art.  +
Article3017 +The Linked Data paradigm introduces the possibility to share machine-readable data across numerous Web resources, thus enabling applications that are traditionally only possible in corporate intranets to be realized on a Web scale. Due to the creation of an increasing number of publicly available Linked Open Data resources, the Web of Data has become a major application area for semantic technologies. This work introduces a recently published data set LON of non-lexical entities (NLEs) that can be used for numerous tasks of quantitative modeling on the Semantic Web. The size of the published data increases the magnitude of the public Linked Data significantly, yet we show how it can be seamlessly integrated into current application architectures for the Web of Data.  +
Article3018 +The Semantic Web comprises enormous volumes of semi-structured data elements. For interoperability, these elements are represented by long strings. Such representations are not efficient for the purposes of applications that perform computations over large volumes of such information. A common approach to alleviate this problem is through the use of compression methods that produce more compact representations of the data. The use of dictionary encoding is particularly prevalent in Semantic Web database systems for this purpose. However, centralized implementations present performance bottlenecks, giving rise to the need for scalable, efficient distributed encoding schemes. In this paper, we propose an efficient algorithm for fast encoding large Semantic Web data. Specially, we present the detailed implementation of our approach based on the state-of-art asynchronous partitioned global address space (APGAS) parallel programming model. We evaluate performance on a cluster of up to 384 cores and datasets of up to 11 billion triples (1.9 TB). Compared to the state-of-art approach, we demonstrate a speed-up of 2.6 - 7.4x and excellent scalability. In the meantime, these results also illustrate the significant potential of the APGAS model for efficient implementation of dictionary encoding and contributes to the engineering of more efficient, larger scale Semantic Web applications.  +
Article3019 +Distributed RDF data management systems become increasingly important with the growth of the Semantic Web. Regardless, current methods meet performance bottlenecks either on data loading or querying when processing large amounts of data. In this work, we propose efficient methods for processing RDF using dynamic data re-partitioning to enable rapid analysis of large datasets. Our approach adopts a two-tier index architecture on each computation node: (1) a lightweight primary index, to keep loading times low, and (2) a series of dynamic, multi-level secondary indexes, calculated as a by-product of query execution, to decrease or remove inter-machine data movement for subsequent queries that contain the same graph patterns. In addition, we propose methods to replace some secondary indexes with distributed filters, so as to decrease memory consumption. Experimental results on a commodity cluster with 16 nodes show that the method presents good scale-out characteristics and can indeed vastly improve loading speeds while remaining competitive in terms of performance. Specifically, our approach can load a dataset of 1.1 billion triples at a rate of 2.48 million triples per second and provide competitive performance to RDF-3X and 4store for expensive queries.  +
(vorherige 25) (nächste 25)