Computational Complexity of Problems on Probabilistic Grammars and Transducers View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2000

AUTHORS

Francisco Casacuberta , Colin de la Higuera

ABSTRACT

Determinism plays an important role in grammatical inference. However, in practice, ambiguous grammars (and non determinism grammars in particular) are more used than determinism grammars. Computing the probability of parsing a given string or its most probable parse with stochastic regular grammars can be performed in linear time. However, the problem of finding the most probable string has yet not given any satisfactory answer. In this paper we prove that the problem is NP-hard and does not allow for a polynomial time approximation scheme. The result extends to stochastic regular syntax-directed translation schemes. More... »

PAGES

15-24

References to SciGraph publications

Book

TITLE

Grammatical Inference: Algorithms and Applications

ISBN

978-3-540-41011-9
978-3-540-45257-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-45257-7_2

DOI

http://dx.doi.org/10.1007/978-3-540-45257-7_2

DIMENSIONS

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


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/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Polytechnic University of Valencia", 
          "id": "https://www.grid.ac/institutes/grid.157927.f", 
          "name": [
            "Departamento de Sistemas Inform\u00e1ticos y Computaci\u00f3n, Universidad Polit\u00e9cnica de Valencia, 46071, Valencia, Spain"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Casacuberta", 
        "givenName": "Francisco", 
        "id": "sg:person.010572020053.79", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010572020053.79"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "EURISE, Facult\u00e9 des Sciences et Techniques, Universit\u00e9 de Saint Etienne \u2013 Jean Monnet, 42023, Saint Etienne, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "de la Higuera", 
        "givenName": "Colin", 
        "id": "sg:person.0614626144.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0614626144.21"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-642-83069-3_35", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005585357", 
          "https://doi.org/10.1007/978-3-642-83069-3_35"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0033362", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007489390", 
          "https://doi.org/10.1007/bfb0033362"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-57745-1_27", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009380616", 
          "https://doi.org/10.1007/978-3-642-57745-1_27"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-57745-1_27", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009380616", 
          "https://doi.org/10.1007/978-3-642-57745-1_27"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-58473-0_141", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013671835", 
          "https://doi.org/10.1007/3-540-58473-0_141"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-58473-0_144", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020984415", 
          "https://doi.org/10.1007/3-540-58473-0_144"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/225298.225302", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021952608"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-3975(97)00014-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024472591"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0885-2308(91)90009-f", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024934091"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-58473-0_146", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031901738", 
          "https://doi.org/10.1007/3-540-58473-0_146"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/322326.322334", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032331779"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1007353007695", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037014576", 
          "https://doi.org/10.1023/a:1007353007695"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(91)90023-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043200457"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1051/ita:1999102", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1056972030"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/34.211465", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061155805"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/34.57687", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061156566"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tsmc.1975.5408432", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061792866"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0218001496000153", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062951047"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2000", 
    "datePublishedReg": "2000-01-01", 
    "description": "Determinism plays an important role in grammatical inference. However, in practice, ambiguous grammars (and non determinism grammars in particular) are more used than determinism grammars. Computing the probability of parsing a given string or its most probable parse with stochastic regular grammars can be performed in linear time. However, the problem of finding the most probable string has yet not given any satisfactory answer. In this paper we prove that the problem is NP-hard and does not allow for a polynomial time approximation scheme. The result extends to stochastic regular syntax-directed translation schemes.", 
    "editor": [
      {
        "familyName": "Oliveira", 
        "givenName": "Arlindo L.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-45257-7_2", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-41011-9", 
        "978-3-540-45257-7"
      ], 
      "name": "Grammatical Inference: Algorithms and Applications", 
      "type": "Book"
    }, 
    "name": "Computational Complexity of Problems on Probabilistic Grammars and Transducers", 
    "pagination": "15-24", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1005228610"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-45257-7_2"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "18e92c4108c2b271ee5ed826aaa9b17e2dfd77f0ea8ed1356037c1e024cc29d4"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-45257-7_2", 
      "https://app.dimensions.ai/details/publication/pub.1005228610"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:02", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000359_0000000359/records_29203_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-45257-7_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-3-540-45257-7_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-3-540-45257-7_2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-45257-7_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-3-540-45257-7_2'


 

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

132 TRIPLES      23 PREDICATES      44 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-45257-7_2 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author N4c2d648aec384a30b23ee18ae96368f9
4 schema:citation sg:pub.10.1007/3-540-58473-0_141
5 sg:pub.10.1007/3-540-58473-0_144
6 sg:pub.10.1007/3-540-58473-0_146
7 sg:pub.10.1007/978-3-642-57745-1_27
8 sg:pub.10.1007/978-3-642-83069-3_35
9 sg:pub.10.1007/bfb0033362
10 sg:pub.10.1023/a:1007353007695
11 https://doi.org/10.1016/0022-0000(91)90023-x
12 https://doi.org/10.1016/0885-2308(91)90009-f
13 https://doi.org/10.1016/s0304-3975(97)00014-5
14 https://doi.org/10.1051/ita:1999102
15 https://doi.org/10.1109/34.211465
16 https://doi.org/10.1109/34.57687
17 https://doi.org/10.1109/tsmc.1975.5408432
18 https://doi.org/10.1142/s0218001496000153
19 https://doi.org/10.1145/225298.225302
20 https://doi.org/10.1145/322326.322334
21 schema:datePublished 2000
22 schema:datePublishedReg 2000-01-01
23 schema:description Determinism plays an important role in grammatical inference. However, in practice, ambiguous grammars (and non determinism grammars in particular) are more used than determinism grammars. Computing the probability of parsing a given string or its most probable parse with stochastic regular grammars can be performed in linear time. However, the problem of finding the most probable string has yet not given any satisfactory answer. In this paper we prove that the problem is NP-hard and does not allow for a polynomial time approximation scheme. The result extends to stochastic regular syntax-directed translation schemes.
24 schema:editor Nab46cd24266248ddbaac4afab4c01e90
25 schema:genre chapter
26 schema:inLanguage en
27 schema:isAccessibleForFree true
28 schema:isPartOf N1c2a7eb9c2f949af80f5a1af883aaa2c
29 schema:name Computational Complexity of Problems on Probabilistic Grammars and Transducers
30 schema:pagination 15-24
31 schema:productId N4d5d38245a3447348bb02367f94b9e22
32 N9a119f47a18543588c6ec46b1a221806
33 Ne19d1c34dd9545cd87ff32944455ea29
34 schema:publisher N9ffd1e9c45e64d068b9662e6bb4409d3
35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005228610
36 https://doi.org/10.1007/978-3-540-45257-7_2
37 schema:sdDatePublished 2019-04-16T08:02
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher N0970f43983ff469c8b6b901ff661e504
40 schema:url https://link.springer.com/10.1007%2F978-3-540-45257-7_2
41 sgo:license sg:explorer/license/
42 sgo:sdDataset chapters
43 rdf:type schema:Chapter
44 N0970f43983ff469c8b6b901ff661e504 schema:name Springer Nature - SN SciGraph project
45 rdf:type schema:Organization
46 N113e22415cc7449d878d8bbcaf5a823e schema:familyName Oliveira
47 schema:givenName Arlindo L.
48 rdf:type schema:Person
49 N1c2a7eb9c2f949af80f5a1af883aaa2c schema:isbn 978-3-540-41011-9
50 978-3-540-45257-7
51 schema:name Grammatical Inference: Algorithms and Applications
52 rdf:type schema:Book
53 N283b40a36d334909ba9bc8a33ab0c376 rdf:first sg:person.0614626144.21
54 rdf:rest rdf:nil
55 N4c2d648aec384a30b23ee18ae96368f9 rdf:first sg:person.010572020053.79
56 rdf:rest N283b40a36d334909ba9bc8a33ab0c376
57 N4d5d38245a3447348bb02367f94b9e22 schema:name dimensions_id
58 schema:value pub.1005228610
59 rdf:type schema:PropertyValue
60 N95811f22621747a7a604df9ea077f47b schema:name EURISE, Faculté des Sciences et Techniques, Université de Saint Etienne – Jean Monnet, 42023, Saint Etienne, France
61 rdf:type schema:Organization
62 N9a119f47a18543588c6ec46b1a221806 schema:name doi
63 schema:value 10.1007/978-3-540-45257-7_2
64 rdf:type schema:PropertyValue
65 N9ffd1e9c45e64d068b9662e6bb4409d3 schema:location Berlin, Heidelberg
66 schema:name Springer Berlin Heidelberg
67 rdf:type schema:Organisation
68 Nab46cd24266248ddbaac4afab4c01e90 rdf:first N113e22415cc7449d878d8bbcaf5a823e
69 rdf:rest rdf:nil
70 Ne19d1c34dd9545cd87ff32944455ea29 schema:name readcube_id
71 schema:value 18e92c4108c2b271ee5ed826aaa9b17e2dfd77f0ea8ed1356037c1e024cc29d4
72 rdf:type schema:PropertyValue
73 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
74 schema:name Mathematical Sciences
75 rdf:type schema:DefinedTerm
76 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
77 schema:name Statistics
78 rdf:type schema:DefinedTerm
79 sg:person.010572020053.79 schema:affiliation https://www.grid.ac/institutes/grid.157927.f
80 schema:familyName Casacuberta
81 schema:givenName Francisco
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010572020053.79
83 rdf:type schema:Person
84 sg:person.0614626144.21 schema:affiliation N95811f22621747a7a604df9ea077f47b
85 schema:familyName de la Higuera
86 schema:givenName Colin
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0614626144.21
88 rdf:type schema:Person
89 sg:pub.10.1007/3-540-58473-0_141 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013671835
90 https://doi.org/10.1007/3-540-58473-0_141
91 rdf:type schema:CreativeWork
92 sg:pub.10.1007/3-540-58473-0_144 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020984415
93 https://doi.org/10.1007/3-540-58473-0_144
94 rdf:type schema:CreativeWork
95 sg:pub.10.1007/3-540-58473-0_146 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031901738
96 https://doi.org/10.1007/3-540-58473-0_146
97 rdf:type schema:CreativeWork
98 sg:pub.10.1007/978-3-642-57745-1_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009380616
99 https://doi.org/10.1007/978-3-642-57745-1_27
100 rdf:type schema:CreativeWork
101 sg:pub.10.1007/978-3-642-83069-3_35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005585357
102 https://doi.org/10.1007/978-3-642-83069-3_35
103 rdf:type schema:CreativeWork
104 sg:pub.10.1007/bfb0033362 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007489390
105 https://doi.org/10.1007/bfb0033362
106 rdf:type schema:CreativeWork
107 sg:pub.10.1023/a:1007353007695 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037014576
108 https://doi.org/10.1023/a:1007353007695
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/0022-0000(91)90023-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043200457
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/0885-2308(91)90009-f schema:sameAs https://app.dimensions.ai/details/publication/pub.1024934091
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/s0304-3975(97)00014-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024472591
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1051/ita:1999102 schema:sameAs https://app.dimensions.ai/details/publication/pub.1056972030
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1109/34.211465 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061155805
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1109/34.57687 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061156566
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1109/tsmc.1975.5408432 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061792866
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1142/s0218001496000153 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062951047
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1145/225298.225302 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021952608
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1145/322326.322334 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032331779
129 rdf:type schema:CreativeWork
130 https://www.grid.ac/institutes/grid.157927.f schema:alternateName Polytechnic University of Valencia
131 schema:name Departamento de Sistemas Informáticos y Computación, Universidad Politécnica de Valencia, 46071, Valencia, Spain
132 rdf:type schema:Organization
 




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


...