1988
AUTHORS ABSTRACTWe present an algebraic model for search problems and their solutions. The model includes in its formalism dynamic programming, branch and bound, and other implicit enumeration techniques. Search problems are defined over a finite set of conjuncts, a nonassociative analogue of strings. The generalization to conjuncts is important because it allows the model to handle naturally problems with objects (e.g., binary trees) that combine in a nonassociative manner. The solution of a search problem requires the identification of a minimal element of the set of feasible conjuncts. We model the solution process in terms of two types of operators. Each of these operators enumerates a set of conjuncts, and in so doing infers the indentity of the only conjunct in the set that can possibly be extended to a minimal feasible conjunct. The operators themselves are based on computationally feasible dominance relations that order certain pairs of conjuncts, and whose axioms allow us to infer the orderings of the feasible extensions of such conjuncts. More... »
PAGES28-90
Search in Artificial Intelligence
ISBN
978-1-4613-8790-9
978-1-4613-8788-6
http://scigraph.springernature.com/pub.10.1007/978-1-4613-8788-6_2
DOIhttp://dx.doi.org/10.1007/978-1-4613-8788-6_2
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1002401971
JSON-LD is the canonical representation for SciGraph data.
TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT
[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
"about": [
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Pure Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Computer Science, University of New Mexico, 87131, Albuquerque, New Mexico, USA",
"id": "http://www.grid.ac/institutes/grid.266832.b",
"name": [
"Department of Computer Science, University of New Mexico, 87131, Albuquerque, New Mexico, USA"
],
"type": "Organization"
},
"familyName": "Helman",
"givenName": "Paul",
"id": "sg:person.01034346234.77",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01034346234.77"
],
"type": "Person"
}
],
"datePublished": "1988",
"datePublishedReg": "1988-01-01",
"description": "We present an algebraic model for search problems and their solutions. The model includes in its formalism dynamic programming, branch and bound, and other implicit enumeration techniques. Search problems are defined over a finite set of conjuncts, a nonassociative analogue of strings. The generalization to conjuncts is important because it allows the model to handle naturally problems with objects (e.g., binary trees) that combine in a nonassociative manner. The solution of a search problem requires the identification of a minimal element of the set of feasible conjuncts. We model the solution process in terms of two types of operators. Each of these operators enumerates a set of conjuncts, and in so doing infers the indentity of the only conjunct in the set that can possibly be extended to a minimal feasible conjunct. The operators themselves are based on computationally feasible dominance relations that order certain pairs of conjuncts, and whose axioms allow us to infer the orderings of the feasible extensions of such conjuncts.",
"editor": [
{
"familyName": "Kanal",
"givenName": "Laveen",
"type": "Person"
},
{
"familyName": "Kumar",
"givenName": "Vipin",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-1-4613-8788-6_2",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-1-4613-8790-9",
"978-1-4613-8788-6"
],
"name": "Search in Artificial Intelligence",
"type": "Book"
},
"keywords": [
"search problem",
"implicit enumeration technique",
"types of operators",
"algebraic model",
"finite set",
"dynamic programming",
"solution process",
"certain pairs",
"feasible extension",
"operators",
"enumeration technique",
"minimal elements",
"dominance relation",
"problem",
"set",
"algebra",
"solution",
"conjuncts",
"programming",
"model",
"generalization",
"ordering",
"objects",
"strings",
"axioms",
"infers",
"extension",
"indentity",
"technique",
"terms",
"branches",
"pairs",
"manner",
"process",
"identification",
"elements",
"relation",
"analogues",
"types"
],
"name": "An Algebra for Search Problems and Their Solutions",
"pagination": "28-90",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1002401971"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-1-4613-8788-6_2"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-1-4613-8788-6_2",
"https://app.dimensions.ai/details/publication/pub.1002401971"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-10T10:43",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_244.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-1-4613-8788-6_2"
}
]
Download the RDF metadata as: json-ld nt turtle xml License info
JSON-LD is a popular format for linked data which is fully compatible with JSON.
curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-1-4613-8788-6_2'
N-Triples is a line-based linked data format ideal for batch operations.
curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-1-4613-8788-6_2'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-1-4613-8788-6_2'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-1-4613-8788-6_2'
This table displays all metadata directly associated to this object as RDF triples.
104 TRIPLES
23 PREDICATES
65 URIs
58 LITERALS
7 BLANK NODES
Subject | Predicate | Object | |
---|---|---|---|
1 | sg:pub.10.1007/978-1-4613-8788-6_2 | schema:about | anzsrc-for:01 |
2 | ″ | ″ | anzsrc-for:0101 |
3 | ″ | schema:author | N53dbfc74ce134dfcbcb74da1d4a706db |
4 | ″ | schema:datePublished | 1988 |
5 | ″ | schema:datePublishedReg | 1988-01-01 |
6 | ″ | schema:description | We present an algebraic model for search problems and their solutions. The model includes in its formalism dynamic programming, branch and bound, and other implicit enumeration techniques. Search problems are defined over a finite set of conjuncts, a nonassociative analogue of strings. The generalization to conjuncts is important because it allows the model to handle naturally problems with objects (e.g., binary trees) that combine in a nonassociative manner. The solution of a search problem requires the identification of a minimal element of the set of feasible conjuncts. We model the solution process in terms of two types of operators. Each of these operators enumerates a set of conjuncts, and in so doing infers the indentity of the only conjunct in the set that can possibly be extended to a minimal feasible conjunct. The operators themselves are based on computationally feasible dominance relations that order certain pairs of conjuncts, and whose axioms allow us to infer the orderings of the feasible extensions of such conjuncts. |
7 | ″ | schema:editor | N4130a362555f40b1b6544e30bc9b281c |
8 | ″ | schema:genre | chapter |
9 | ″ | schema:inLanguage | en |
10 | ″ | schema:isAccessibleForFree | false |
11 | ″ | schema:isPartOf | N2251e1593608485882f5f7b293f9675a |
12 | ″ | schema:keywords | algebra |
13 | ″ | ″ | algebraic model |
14 | ″ | ″ | analogues |
15 | ″ | ″ | axioms |
16 | ″ | ″ | branches |
17 | ″ | ″ | certain pairs |
18 | ″ | ″ | conjuncts |
19 | ″ | ″ | dominance relation |
20 | ″ | ″ | dynamic programming |
21 | ″ | ″ | elements |
22 | ″ | ″ | enumeration technique |
23 | ″ | ″ | extension |
24 | ″ | ″ | feasible extension |
25 | ″ | ″ | finite set |
26 | ″ | ″ | generalization |
27 | ″ | ″ | identification |
28 | ″ | ″ | implicit enumeration technique |
29 | ″ | ″ | indentity |
30 | ″ | ″ | infers |
31 | ″ | ″ | manner |
32 | ″ | ″ | minimal elements |
33 | ″ | ″ | model |
34 | ″ | ″ | objects |
35 | ″ | ″ | operators |
36 | ″ | ″ | ordering |
37 | ″ | ″ | pairs |
38 | ″ | ″ | problem |
39 | ″ | ″ | process |
40 | ″ | ″ | programming |
41 | ″ | ″ | relation |
42 | ″ | ″ | search problem |
43 | ″ | ″ | set |
44 | ″ | ″ | solution |
45 | ″ | ″ | solution process |
46 | ″ | ″ | strings |
47 | ″ | ″ | technique |
48 | ″ | ″ | terms |
49 | ″ | ″ | types |
50 | ″ | ″ | types of operators |
51 | ″ | schema:name | An Algebra for Search Problems and Their Solutions |
52 | ″ | schema:pagination | 28-90 |
53 | ″ | schema:productId | N03e4ac5045b248f5919e90d0e800d297 |
54 | ″ | ″ | Nc9875b82e0fc4c9595e97b13fda7cce5 |
55 | ″ | schema:publisher | N7d5c492e1693434d9db8a31f10b51417 |
56 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1002401971 |
57 | ″ | ″ | https://doi.org/10.1007/978-1-4613-8788-6_2 |
58 | ″ | schema:sdDatePublished | 2022-05-10T10:43 |
59 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |
60 | ″ | schema:sdPublisher | N7f2acc69de9b4965bcf4063dd2b0ad40 |
61 | ″ | schema:url | https://doi.org/10.1007/978-1-4613-8788-6_2 |
62 | ″ | sgo:license | sg:explorer/license/ |
63 | ″ | sgo:sdDataset | chapters |
64 | ″ | rdf:type | schema:Chapter |
65 | N03e4ac5045b248f5919e90d0e800d297 | schema:name | doi |
66 | ″ | schema:value | 10.1007/978-1-4613-8788-6_2 |
67 | ″ | rdf:type | schema:PropertyValue |
68 | N20131f951c6a4d778fd3dfd5c3f3f9b3 | schema:familyName | Kanal |
69 | ″ | schema:givenName | Laveen |
70 | ″ | rdf:type | schema:Person |
71 | N2251e1593608485882f5f7b293f9675a | schema:isbn | 978-1-4613-8788-6 |
72 | ″ | ″ | 978-1-4613-8790-9 |
73 | ″ | schema:name | Search in Artificial Intelligence |
74 | ″ | rdf:type | schema:Book |
75 | N4130a362555f40b1b6544e30bc9b281c | rdf:first | N20131f951c6a4d778fd3dfd5c3f3f9b3 |
76 | ″ | rdf:rest | Na4c427ee1217428585b9ae094b6e5a64 |
77 | N53dbfc74ce134dfcbcb74da1d4a706db | rdf:first | sg:person.01034346234.77 |
78 | ″ | rdf:rest | rdf:nil |
79 | N6c1f0c4eb2f14c25a5d20b8c7356594c | schema:familyName | Kumar |
80 | ″ | schema:givenName | Vipin |
81 | ″ | rdf:type | schema:Person |
82 | N7d5c492e1693434d9db8a31f10b51417 | schema:name | Springer Nature |
83 | ″ | rdf:type | schema:Organisation |
84 | N7f2acc69de9b4965bcf4063dd2b0ad40 | schema:name | Springer Nature - SN SciGraph project |
85 | ″ | rdf:type | schema:Organization |
86 | Na4c427ee1217428585b9ae094b6e5a64 | rdf:first | N6c1f0c4eb2f14c25a5d20b8c7356594c |
87 | ″ | rdf:rest | rdf:nil |
88 | Nc9875b82e0fc4c9595e97b13fda7cce5 | schema:name | dimensions_id |
89 | ″ | schema:value | pub.1002401971 |
90 | ″ | rdf:type | schema:PropertyValue |
91 | anzsrc-for:01 | schema:inDefinedTermSet | anzsrc-for: |
92 | ″ | schema:name | Mathematical Sciences |
93 | ″ | rdf:type | schema:DefinedTerm |
94 | anzsrc-for:0101 | schema:inDefinedTermSet | anzsrc-for: |
95 | ″ | schema:name | Pure Mathematics |
96 | ″ | rdf:type | schema:DefinedTerm |
97 | sg:person.01034346234.77 | schema:affiliation | grid-institutes:grid.266832.b |
98 | ″ | schema:familyName | Helman |
99 | ″ | schema:givenName | Paul |
100 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01034346234.77 |
101 | ″ | rdf:type | schema:Person |
102 | grid-institutes:grid.266832.b | schema:alternateName | Department of Computer Science, University of New Mexico, 87131, Albuquerque, New Mexico, USA |
103 | ″ | schema:name | Department of Computer Science, University of New Mexico, 87131, Albuquerque, New Mexico, USA |
104 | ″ | rdf:type | schema:Organization |