Zobrazeno 1 - 10
of 185
pro vyhledávání: '"Peter Jonsson"'
Publikováno v:
Computational Linguistics, Vol 44, Iss 3, Pp 447-482 (2018)
We study the parsing complexity of Combinatory Categorial Grammar (CCG) in the formalism of Vijay-Shanker and Weir (1994). As our main result, we prove that any parsing algorithm for this formalism will take in the worst case exponential time when th
Externí odkaz:
https://doaj.org/article/d8430fc61c2b44f1b27abd11c00080f2
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol Vol. 17 no. 1, Iss Graph Theory (2015)
Graph Theory
Externí odkaz:
https://doaj.org/article/5372346a63d94b86823d9b69948a989f
Publikováno v:
Logical Methods in Computer Science, Vol Volume 8, Issue 4 (2012)
Let \Gamma be a structure with a finite relational signature and a first-order definition in (R;*,+) with parameters from R, that is, a relational structure over the real numbers where all relations are semi-algebraic sets. In this article, we study
Externí odkaz:
https://doaj.org/article/04573407603f4c1d96d62689a9e831ce
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol DMTCS Proceedings vol. AE,..., Iss Proceedings (2005)
In the maximum constraint satisfaction problem ($\mathrm{Max \; CSP}$), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given finite domain to the variables
Externí odkaz:
https://doaj.org/article/d60aa92b2c6f4346aad232d31b24e529
Autor:
Peter Jonsson, Victor Lagerkvist
Publikováno v:
Algorithmica. 85:188-215
We study the fine-grained complexity of NP-complete, infinite-domain constraint satisfaction problems (CSPs) parameterised by a set of first-order definable relations (with equality). Such CSPs are of central importance since they form a subclass of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::95c09aa1dd45d2a26b82dabdd5f01d22
https://doi.org/10.1007/s00453-022-01017-8
https://doi.org/10.1007/s00453-022-01017-8
Publikováno v:
Proceedings of the AAAI Conference on Artificial Intelligence. 36:3724-3732
The simple temporal problem (STP) is one of the most influential reasoning formalisms for representing temporal information in AI. We study the problem of resolving inconsistency of data encoded in the STP. We prove that the problem of identifying a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2a0d7660432ba0b3e2ae721494090f2e
https://doi.org/10.1609/aaai.v36i4.20286
https://doi.org/10.1609/aaai.v36i4.20286
Autor:
Christer Backstrom, Peter Jonsson
Publikováno v:
Proceedings of the International Symposium on Combinatorial Search. 3:10-17
Modelling abstraction as a function from the original state space to an abstract state space is a common approach in combinatorial search. Sometimes this is too restricted, though, and we have previously proposed a framework using a more flexible con
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ccc803b05b39d8a1de46bce7cf53d18e
https://doi.org/10.1609/socs.v3i1.18240
https://doi.org/10.1609/socs.v3i1.18240
Publikováno v:
Proceedings of the International Symposium on Combinatorial Search. 4:29-37
There has been a tremendous advance in domain-independent planning over the past decades, and planners have become increasingly efficient at finding plans. However, this has not been paired by any corresponding improvement in detecting unsolvable ins
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::89eeca0f5dd5ff6cd18d6665b700631f
https://doi.org/10.1609/socs.v4i1.18294
https://doi.org/10.1609/socs.v4i1.18294
Autor:
Christer Backstrom, Peter Jonsson
Publikováno v:
Proceedings of the International Symposium on Combinatorial Search. 2:10-17
Complexity analysis of planning is problematic. Even very simple planning languages are PSPACE-complete, yet cannot model many simple problems naturally. Many languages with much more powerful features are also PSPACE-complete. It is thus difficult t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7a4fe98871f95f34502b6c6834f84664
https://doi.org/10.1609/socs.v2i1.18186
https://doi.org/10.1609/socs.v2i1.18186
Autor:
Peter Jonsson, Alexander Shleyfman
Publikováno v:
Journal of Artificial Intelligence Research. 70:1183-1221
Symmetry-based pruning is a powerful method for reducing the search effort in finitedomain planning. This method is based on exploiting an automorphism group connected to the ground description of the planning task - these automorphisms are known as
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2377d2b530e17d9b9600d851678f6d6b
https://doi.org/10.1613/jair.1.12283
https://doi.org/10.1613/jair.1.12283