| 1. |
- Bäckström, Christer, 1962-, et al.
(författare)
-
Novel Structural Parameters for Acyclic Planning Using Tree Embeddings
- 2018
-
Ingår i: 27th International Joint Conference on Artificial Intelligence. - California : International Joint Conferences on Artificial Intelligence Organization. - 9780999241127 ; , s. 4653-4659
-
Konferensbidrag (refereegranskat)abstract
- We introduce two novel structural parameters for acyclic planning (planning restricted to instances with acyclic causal graphs): up-depth and down-depth. We show that cost-optimal acyclic planning restricted to instances with bounded domain size and bounded up- or down-depth can be solved in polynomial time. For example, many of the tractable subclasses based on polytrees are covered by our result. We analyze the parameterized complexity of planning with bounded up- and down-depth: in a certain sense, down-depth has better computational properties than up-depth. Finally, we show that computing up- and down-depth are fixed-parameter tractable problems, just as many other structural parameters that are used in computer science. We view our results as a natural step towards understanding the complexity of acyclic planning with bounded treewidth and other parameters.
|
|
| 2. |
- Hartig, Olaf, 1976-, et al.
(författare)
-
A Model of Distributed Query Computation in Client-Server Scenarios on the Semantic Web
- 2018
-
Ingår i: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden. - California : AAAI Press. - 9780999241127 ; , s. 5259-5263
-
Konferensbidrag (refereegranskat)abstract
- This paper provides an overview of a model for capturing properties of client-server-based query computation setups. This model can be used to formally analyze different combinations of client and server capabilities, and compare them in terms of various fine-grain complexity measures. While the motivations and the focus of the presented work are related to querying the Semantic Web, the main concepts of the model are general enough to be applied in other contexts as well.
|
|
| 3. |
- Kolb, Samuel, et al.
(författare)
-
Learning SMT(LRA) Constraints using SMT Solvers
- 2018
-
Ingår i: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. - California : AAAI Press. - 9780999241127 ; , s. 2333-2340
-
Konferensbidrag (refereegranskat)abstract
- We introduce the problem of learning SMT(LRA) constraints from data. SMT(LRA) extends propositional logic with (in)equalities between numerical variables. Many relevant formal verification problems can be cast as SMT(LRA) instances and SMT(LRA) has supported recent developments in optimization and counting for hybrid Boolean and numerical domains. We introduce SMT(LRA)learning, the task of learning SMT(LRA) formulas from examples of feasible and infeasible instances, and we contribute INCAL, an exact non-greedy algorithm for this setting. Our approach encodes the learning task itself as an SMT(LRA) satisfiability problem that can be solved directly by SMT solvers. INCAL is an incremental algorithm that achieves exact learning by looking only at a small subset of the data, leading to significant speed-ups. We empirically evaluate our approach on both synthetic instances and benchmark problems taken from the SMT-LIB benchmarks repository.
|
|
