Existential Omega-entailment is a para consistent entailment relation designed to show the consequences of data which is inconsistent with a set of integrity constraints Omega. In this paper, we prove semantic propert...
详细信息
Existential Omega-entailment is a para consistent entailment relation designed to show the consequences of data which is inconsistent with a set of integrity constraints Omega. In this paper, we prove semantic properties of existential Omega-entailment and give an algorithm for computing it.
Query containment has been studied extensively in KR and databases, for different kinds of query languages and domain constraints. We address the longstanding open problem of containment under expressive description l...
详细信息
ISBN:
(纸本)9781577355120
Query containment has been studied extensively in KR and databases, for different kinds of query languages and domain constraints. We address the longstanding open problem of containment under expressive description logic (DL) constraints for two-way regular path queries (2RPQs) and their conjunctions, which generalize conjunctive queries with the ability to express regular navigation. We show that, surprisingly, functionality constraints alone make containment of 2RPQs already EXPTIME-hard. By employing automatatheoretic techniques, we also provide a matching upper bound that extends to very expressive DL constraints. For conjunctive 2RPQs we prove a further exponential jump in complexity, and provide again a matching upper bound for expressive DLs. Our techniques provide also a solution to the problem of query entailment over DL knowledge bases in which individuals in the ABox may be related through regular role-paths.
An elegant approach to learning temporal orderings from texts is to formulate this problem as a constraint optimization problem, which can be then given an exact solution using Integer Linear programming. This works w...
详细信息
ISBN:
(纸本)9781577355120
An elegant approach to learning temporal orderings from texts is to formulate this problem as a constraint optimization problem, which can be then given an exact solution using Integer Linear programming. This works well for cases where the number of possible relations between temporal entities is restricted to the mere precedence relation [Bramsen et al., 2006;Chambers and Jurafsky, 2008], but becomes impractical when considering all possible interval relations. This paper proposes two innovations, inspired from work on temporal reasoning, that control this combinatorial blow-up, therefore rendering an exact ILP inference viable in the general case. First, we translate our network of constraints from temporal intervals to their endpoints, to handle a drastically smaller set of constraints, while preserving the same temporal information. Second, we show that additional efficiency is gained by enforcing coherence on particular subsets of the entire temporal graphs. We evaluate these innovations through various experiments on TimeBank 1.2, and compare our ILP formulations with various baselines and oracle systems.
Many collective decision making problems have a combinatorial structure: the agents involved must decide on multiple issues and their preferences over one issue may depend on the choices adopted for some of the others...
ISBN:
(纸本)9781577355120
Many collective decision making problems have a combinatorial structure: the agents involved must decide on multiple issues and their preferences over one issue may depend on the choices adopted for some of the others. Voting is an attractive method for making collective decisions, but conducting a multi-issue election is challenging. On the one hand, requiring agents to vote by expressing their preferences over all combinations of issues is computationally infeasible;on the other, decomposing the problem into several elections on smaller sets of issues can lead to paradoxical outcomes. Any pragmatic method for running a multi-issue election will have to balance these two concerns. We identify and analyse the problem of generating an agenda for a given election, specifying which issues to vote on together in local elections and in which order to schedule those local elections.
Classical constraint satisfaction problems (CSPs) are commonly defined on finite domains. In real life, constrained variables can evolve over time. A variable can actually take an infinite sequence of values over disc...
详细信息
ISBN:
(纸本)9781577355120
Classical constraint satisfaction problems (CSPs) are commonly defined on finite domains. In real life, constrained variables can evolve over time. A variable can actually take an infinite sequence of values over discrete time points. In this paper, we propose constraint programming on infinite data streams, which provides a natural way to model constrained time-varying problems. In our framework, variable domains are specified by ω-regular languages. We introduce special stream operators as basis to form stream expressions and constraints. Stream CSPs have infinite search space. We propose a search procedure that can recognize and avoid infinite search over duplicate search space. The solution set of a stream CSP can be represented by a Büchi automaton allowing stream values to be non-periodic. Consistency notions are defined to reduce the search space early. We illustrate the feasibility of the framework by examples and experiments.
[Fages, 1994] introduces the notion of well-supportedness as a key requirement for the semantics of normal logic programs and characterizes the standard answer set semantics in terms of the well-supportedness conditio...
详细信息
ISBN:
(纸本)9781577355120
[Fages, 1994] introduces the notion of well-supportedness as a key requirement for the semantics of normal logic programs and characterizes the standard answer set semantics in terms of the well-supportedness condition. With the property of well-supportedness, answer sets are guaranteed to be free of circular justifications. In this paper, we extend Fages' work to description logic programs (or DL-programs). We introduce two forms of well-supportedness for DL-programs. The first one defines weakly well-supported models that are free of circular justifications caused by positive literals in rule bodies. The second one defines strongly well-supported models that are free of circular justifications caused by either positive or negative literals. We then define two new answer set semantics for DL-programs and characterize them in terms of the weakly and strongly well-supported models, respectively. The first semantics is based on an extended Gelfond-Lifschitz transformation and defines weakly well-supported answer sets that are free of circular justifications for the class of DL-programs without negative dlatoms. The second semantics defines strongly wellsupported answer sets which are free of circular justifications for all DL-programs. We show that the existing answer set semantics for DL-programs, such as the weak answer set semantics, the strong answer set semantics, and the FLP-based answer set semantics, satisfy neither the weak nor the strong well-supportedness condition, even for DL-programs without negative dl-atoms. This explains why their answer sets incur circular justifications.
The Residue Logarithmic Number System (RLNS) uses the Residue Number System (RNS) to represent logarithms that represent real values. Multiplication and division are easy; reasonable-precision addition and subtraction...
详细信息
The Residue Logarithmic Number System (RLNS) uses the Residue Number System (RNS) to represent logarithms that represent real values. Multiplication and division are easy; reasonable-precision addition and subtraction have not been economical because of RNS sign-detection. This paper adapts novel interpolation (for addition) and cotransformation (for subtraction) to fit the sign-detection limits. Smaller than prior RLNS hardware, the novel ALU defers sign detection with two speculative datapaths.
In this paper we will briefly touch distinctive characteristics of the generations known as baby boomers, generation x, generation y, and generation z; and then propose the use of e-portfolio (EP) as a learning and te...
详细信息
In this paper we will briefly touch distinctive characteristics of the generations known as baby boomers, generation x, generation y, and generation z; and then propose the use of e-portfolio (EP) as a learning and teaching tool and show how it aligns with the aspirations and values of the coming generation. With this respect a 7 week experiment on using EP in “Object Oriented programming” course is run and the results of the instruments applied both before and after the experiment are analyzed to see if there is any change in the attitudes of the students towards using EP and their learning.
The proceedings contain 26 papers. The special focus in this conference is on Modelling, monitoring and management of air pollution. The topics include: Information flow containment;re-designing the web’s access cont...
ISBN:
(纸本)9783642223471
The proceedings contain 26 papers. The special focus in this conference is on Modelling, monitoring and management of air pollution. The topics include: Information flow containment;re-designing the web’s access control system;integrated management of security policies;cooperative data access in multi-cloud environments;multiparty authorization framework for data sharing in online social networks;enforcing confidentiality and data visibility constraints;public-key encrypted bloom filters with applications to supply chain integrity;an optimization model for the extended role mining problem;dynamics in delegation and revocation schemes;history-dependent inference control of queries by dynamic policy adaption;multilevel secure data stream processing;query processing in private data outsourcing using anonymization;private database search with sublinear query time;efficient distributed linear programming with limited disclosure;privacy-preserving data mining: a game-theoretic approach;enhancing cardspace authentication using a mobile device;verifiable secret sharing with comprehensive and efficient public verification;a robust remote user authentication scheme against smart card security breach;N-Gram based secure similar document detection;an index structure for private data outsourcing;selective disclosure on encrypted documents;a new leakage-resilient IBE scheme in the relative leakage model;accurate accident reconstruction in VANET;cyber situation awareness: modeling the security analyst in a cyber-attack scenario through instance-based learning;leveraging UML for security engineering and enforcement in a collaboration on duty and adaptive workflow model that extends NIST RBAC and preserving privacy in structural neuroimages.
This book constitutes the refereed proceedings of the international RuleML Symposium, RuleML 2011-America, held in Fort Lauderdale, FL, USA, in November 2011 - collocated with the 22ndinternational Joint conference o...
ISBN:
(数字)9783642249082
ISBN:
(纸本)9783642249075
This book constitutes the refereed proceedings of the international RuleML Symposium, RuleML 2011-America, held in Fort Lauderdale, FL, USA, in November 2011 - collocated with the 22ndinternational Joint conference on Artificial Intelligence, IJCAI 2011. It is the second of two RuleML events that take place in 2011. The first RuleML Symposium, RuleML 2011-Europe, has been held in Barcelona, Spain, in July 2011. The 12 full papers, 5 short papers and 5 invited track and position papers presented together with 3 keynote speeches were carefully reviewed and selected from numerous submissions. The accepted papers address a wide range of rules, semantic technology, and cross-industry standards, rules and automated reasoning, rule-based event processing and reaction rules, vocabularies, ontologies and business rules, cloud computing and rules, clinical semantics and rules.
暂无评论