An Algebra for Search Problems and Their Solutions View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1988

AUTHORS

Paul Helman

ABSTRACT

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. More... »

PAGES

28-90

Book

TITLE

Search in Artificial Intelligence

ISBN

978-1-4613-8790-9
978-1-4613-8788-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-1-4613-8788-6_2

DOI

http://dx.doi.org/10.1007/978-1-4613-8788-6_2

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1002401971


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

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

HOW TO GET THIS DATA PROGRAMMATICALLY:

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
 




Preview window. Press ESC to close (or click here)


...