Restricted Global Grammar Constraints View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

George Katsirelos , Sebastian Maneth , Nina Narodytska , Toby Walsh

ABSTRACT

We investigate the global Grammar constraint over restricted classes of context free grammars like deterministic and unambiguous context-free grammars. We show that detecting disentailment for the Grammar constraint in these cases is as hard as parsing an unrestricted context free grammar.We also consider the class of linear grammars and give a propagator that runs in quadratic time. Finally, to demonstrate the use of linear grammars, we show that a weighted linear Grammar constraint can efficiently encode the EditDistance constraint, and a conjunction of the EditDistance constraint and the Regular constraint. More... »

PAGES

501-508

Book

TITLE

Principles and Practice of Constraint Programming - CP 2009

ISBN

978-3-642-04243-0
978-3-642-04244-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-04244-7_40

DOI

http://dx.doi.org/10.1007/978-3-642-04244-7_40

DIMENSIONS

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


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/11", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Medical and Health Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1117", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Public Health and Health Services", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "NICTA, Sydney, Australia", 
          "id": "http://www.grid.ac/institutes/grid.425461.0", 
          "name": [
            "NICTA, Sydney, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Katsirelos", 
        "givenName": "George", 
        "id": "sg:person.015303135253.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015303135253.63"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "NICTA and University of NSW, Sydney, Australia", 
          "id": "http://www.grid.ac/institutes/grid.1005.4", 
          "name": [
            "NICTA and University of NSW, Sydney, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Maneth", 
        "givenName": "Sebastian", 
        "id": "sg:person.016240662443.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016240662443.33"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "NICTA and University of NSW, Sydney, Australia", 
          "id": "http://www.grid.ac/institutes/grid.1005.4", 
          "name": [
            "NICTA and University of NSW, Sydney, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Narodytska", 
        "givenName": "Nina", 
        "id": "sg:person.016267314737.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016267314737.51"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "NICTA and University of NSW, Sydney, Australia", 
          "id": "http://www.grid.ac/institutes/grid.1005.4", 
          "name": [
            "NICTA and University of NSW, Sydney, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Walsh", 
        "givenName": "Toby", 
        "id": "sg:person.016152454637.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016152454637.18"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "We investigate the global Grammar constraint over restricted classes of context free grammars like deterministic and unambiguous context-free grammars. We show that detecting disentailment for the Grammar constraint in these cases is as hard as parsing an unrestricted context free grammar.We also consider the class of linear grammars and give a propagator that runs in quadratic time. Finally, to demonstrate the use of linear grammars, we show that a weighted linear Grammar constraint can efficiently encode the EditDistance constraint, and a conjunction of the EditDistance constraint and the Regular constraint.", 
    "editor": [
      {
        "familyName": "Gent", 
        "givenName": "Ian P.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-04244-7_40", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-04243-0", 
        "978-3-642-04244-7"
      ], 
      "name": "Principles and Practice of Constraint Programming - CP 2009", 
      "type": "Book"
    }, 
    "keywords": [
      "cases", 
      "use", 
      "time", 
      "conjunction", 
      "class", 
      "constraints", 
      "grammar", 
      "linear grammars", 
      "grammar constraints", 
      "context free grammar", 
      "free grammars", 
      "context-free grammars", 
      "quadratic time", 
      "regular constraints", 
      "unambiguous context-free grammar", 
      "disentailment", 
      "propagator", 
      "global Grammar constraint", 
      "unrestricted context free grammar", 
      "linear Grammar constraint", 
      "EditDistance constraint"
    ], 
    "name": "Restricted Global Grammar Constraints", 
    "pagination": "501-508", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1015286607"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-04244-7_40"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-04244-7_40", 
      "https://app.dimensions.ai/details/publication/pub.1015286607"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:48", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_162.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-04244-7_40"
  }
]
 

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-3-642-04244-7_40'

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-3-642-04244-7_40'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-04244-7_40'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-04244-7_40'


 

This table displays all metadata directly associated to this object as RDF triples.

105 TRIPLES      23 PREDICATES      47 URIs      40 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-04244-7_40 schema:about anzsrc-for:11
2 anzsrc-for:1117
3 schema:author N9b38cd6ae56e4250a3a7008bc432cf44
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description We investigate the global Grammar constraint over restricted classes of context free grammars like deterministic and unambiguous context-free grammars. We show that detecting disentailment for the Grammar constraint in these cases is as hard as parsing an unrestricted context free grammar.We also consider the class of linear grammars and give a propagator that runs in quadratic time. Finally, to demonstrate the use of linear grammars, we show that a weighted linear Grammar constraint can efficiently encode the EditDistance constraint, and a conjunction of the EditDistance constraint and the Regular constraint.
7 schema:editor N70f6b8506c054570bf4ed9b28abb23a2
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nc7d60ebb9a894f83977629bcf9160aba
12 schema:keywords EditDistance constraint
13 cases
14 class
15 conjunction
16 constraints
17 context free grammar
18 context-free grammars
19 disentailment
20 free grammars
21 global Grammar constraint
22 grammar
23 grammar constraints
24 linear Grammar constraint
25 linear grammars
26 propagator
27 quadratic time
28 regular constraints
29 time
30 unambiguous context-free grammar
31 unrestricted context free grammar
32 use
33 schema:name Restricted Global Grammar Constraints
34 schema:pagination 501-508
35 schema:productId N46b7c6b8d1c14682b6fc5f91b5444af1
36 N7661c6fd7c2d44159140094673c55f7e
37 schema:publisher N98aef5e94d65479ba0faed9734c840cb
38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015286607
39 https://doi.org/10.1007/978-3-642-04244-7_40
40 schema:sdDatePublished 2021-11-01T18:48
41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
42 schema:sdPublisher N793cc74c61004fd0a0bf1be3d69f11cf
43 schema:url https://doi.org/10.1007/978-3-642-04244-7_40
44 sgo:license sg:explorer/license/
45 sgo:sdDataset chapters
46 rdf:type schema:Chapter
47 N16c65ece70fe40479148488297f84269 rdf:first sg:person.016267314737.51
48 rdf:rest Nb529c9a08b5047a79397f8c322fd919c
49 N46b7c6b8d1c14682b6fc5f91b5444af1 schema:name dimensions_id
50 schema:value pub.1015286607
51 rdf:type schema:PropertyValue
52 N47851c5ef6184c2fb1d139a816dd2e16 schema:familyName Gent
53 schema:givenName Ian P.
54 rdf:type schema:Person
55 N70f6b8506c054570bf4ed9b28abb23a2 rdf:first N47851c5ef6184c2fb1d139a816dd2e16
56 rdf:rest rdf:nil
57 N7661c6fd7c2d44159140094673c55f7e schema:name doi
58 schema:value 10.1007/978-3-642-04244-7_40
59 rdf:type schema:PropertyValue
60 N793cc74c61004fd0a0bf1be3d69f11cf schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 N98aef5e94d65479ba0faed9734c840cb schema:name Springer Nature
63 rdf:type schema:Organisation
64 N9b38cd6ae56e4250a3a7008bc432cf44 rdf:first sg:person.015303135253.63
65 rdf:rest Nfda0c2febf9245eb92ade373de02cf5d
66 Nb529c9a08b5047a79397f8c322fd919c rdf:first sg:person.016152454637.18
67 rdf:rest rdf:nil
68 Nc7d60ebb9a894f83977629bcf9160aba schema:isbn 978-3-642-04243-0
69 978-3-642-04244-7
70 schema:name Principles and Practice of Constraint Programming - CP 2009
71 rdf:type schema:Book
72 Nfda0c2febf9245eb92ade373de02cf5d rdf:first sg:person.016240662443.33
73 rdf:rest N16c65ece70fe40479148488297f84269
74 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
75 schema:name Medical and Health Sciences
76 rdf:type schema:DefinedTerm
77 anzsrc-for:1117 schema:inDefinedTermSet anzsrc-for:
78 schema:name Public Health and Health Services
79 rdf:type schema:DefinedTerm
80 sg:person.015303135253.63 schema:affiliation grid-institutes:grid.425461.0
81 schema:familyName Katsirelos
82 schema:givenName George
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015303135253.63
84 rdf:type schema:Person
85 sg:person.016152454637.18 schema:affiliation grid-institutes:grid.1005.4
86 schema:familyName Walsh
87 schema:givenName Toby
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016152454637.18
89 rdf:type schema:Person
90 sg:person.016240662443.33 schema:affiliation grid-institutes:grid.1005.4
91 schema:familyName Maneth
92 schema:givenName Sebastian
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016240662443.33
94 rdf:type schema:Person
95 sg:person.016267314737.51 schema:affiliation grid-institutes:grid.1005.4
96 schema:familyName Narodytska
97 schema:givenName Nina
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016267314737.51
99 rdf:type schema:Person
100 grid-institutes:grid.1005.4 schema:alternateName NICTA and University of NSW, Sydney, Australia
101 schema:name NICTA and University of NSW, Sydney, Australia
102 rdf:type schema:Organization
103 grid-institutes:grid.425461.0 schema:alternateName NICTA, Sydney, Australia
104 schema:name NICTA, Sydney, Australia
105 rdf:type schema:Organization
 




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


...