Compiling Generalized Two-Level Rules and Grammars View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Anssi Yli-Jyrä , Kimmo Koskenniemi

ABSTRACT

New methods to compile morphophonological two-level rules into finite-state machines are presented. Compilation of the original and new two-level rules and grammars is formulated using an operation called the generalized restriction that constructs a one-tape finite-state automaton over an input alphabet of symbol pairs. The generalized restriction is first used to compile the original two-level formalism where the rules were restricted to single symbol pairs as their centers (i.e. the left-hand sides of the rules). The solution handles also strings of symbol pairs (or regular expressions over the pair alphabet) as centers of two-level rules. Then, the treatment of context conditions is generalized with unions and relative complements etc. Moreover, an extended rule type, the presence requirement, combines the generalized context conditions with center conditions at both sides of the rules. The left-hand side specifies where the rule applies and the right-hand side specifies which of the applications are successful. The original two-level grammars were represented as a separate finite-state machine for each rule and the whole grammar as their intersection. The new methods are used first to redefine this setup, and then to implement a uniform conflict resolution scheme for all rules. The resolution scheme prefers successful and the longest embedded applications of rules, but it treats partially overlapping or explicitly independent applications of rules conjunctively. The composite rules of the original formalism have a marginal status in the new formalism because only identity pairs are allowed in locations where no rule is applicable. More... »

PAGES

174-185

Book

TITLE

Advances in Natural Language Processing

ISBN

978-3-540-37334-6
978-3-540-37336-0

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11816508_19

DOI

http://dx.doi.org/10.1007/11816508_19

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Helsinki", 
          "id": "https://www.grid.ac/institutes/grid.7737.4", 
          "name": [
            "Language Bank Service, CSC Scientific Computing Ltd., Finland", 
            "Department of General Linguistics, University of Helsinki, Finland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yli-Jyr\u00e4", 
        "givenName": "Anssi", 
        "id": "sg:person.01066210767.64", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01066210767.64"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Helsinki", 
          "id": "https://www.grid.ac/institutes/grid.7737.4", 
          "name": [
            "Language Bank Service, CSC Scientific Computing Ltd., Finland", 
            "Department of General Linguistics, University of Helsinki, Finland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Koskenniemi", 
        "givenName": "Kimmo", 
        "id": "sg:person.014251223113.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014251223113.28"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.3115/991365.991445", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021646659"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.3115/993268.993277", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048349603"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "New methods to compile morphophonological two-level rules into finite-state machines are presented. Compilation of the original and new two-level rules and grammars is formulated using an operation called the generalized restriction that constructs a one-tape finite-state automaton over an input alphabet of symbol pairs. The generalized restriction is first used to compile the original two-level formalism where the rules were restricted to single symbol pairs as their centers (i.e. the left-hand sides of the rules). The solution handles also strings of symbol pairs (or regular expressions over the pair alphabet) as centers of two-level rules. Then, the treatment of context conditions is generalized with unions and relative complements etc. Moreover, an extended rule type, the presence requirement, combines the generalized context conditions with center conditions at both sides of the rules. The left-hand side specifies where the rule applies and the right-hand side specifies which of the applications are successful. The original two-level grammars were represented as a separate finite-state machine for each rule and the whole grammar as their intersection. The new methods are used first to redefine this setup, and then to implement a uniform conflict resolution scheme for all rules. The resolution scheme prefers successful and the longest embedded applications of rules, but it treats partially overlapping or explicitly independent applications of rules conjunctively. The composite rules of the original formalism have a marginal status in the new formalism because only identity pairs are allowed in locations where no rule is applicable.", 
    "editor": [
      {
        "familyName": "Salakoski", 
        "givenName": "Tapio", 
        "type": "Person"
      }, 
      {
        "familyName": "Ginter", 
        "givenName": "Filip", 
        "type": "Person"
      }, 
      {
        "familyName": "Pyysalo", 
        "givenName": "Sampo", 
        "type": "Person"
      }, 
      {
        "familyName": "Pahikkala", 
        "givenName": "Tapio", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11816508_19", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-37334-6", 
        "978-3-540-37336-0"
      ], 
      "name": "Advances in Natural Language Processing", 
      "type": "Book"
    }, 
    "name": "Compiling Generalized Two-Level Rules and Grammars", 
    "pagination": "174-185", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1039928418"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11816508_19"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "be340229b3f3f0257fb14756e09b9aaab1b7be386345d5a5e1992e7895f43c1e"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11816508_19", 
      "https://app.dimensions.ai/details/publication/pub.1039928418"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T07:29", 
    "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/0000000356_0000000356/records_57865_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F11816508_19"
  }
]
 

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/11816508_19'

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/11816508_19'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11816508_19'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11816508_19'


 

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

94 TRIPLES      23 PREDICATES      29 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11816508_19 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nb7099e1e7b454f22a693121c879a6f2b
4 schema:citation https://doi.org/10.3115/991365.991445
5 https://doi.org/10.3115/993268.993277
6 schema:datePublished 2006
7 schema:datePublishedReg 2006-01-01
8 schema:description New methods to compile morphophonological two-level rules into finite-state machines are presented. Compilation of the original and new two-level rules and grammars is formulated using an operation called the generalized restriction that constructs a one-tape finite-state automaton over an input alphabet of symbol pairs. The generalized restriction is first used to compile the original two-level formalism where the rules were restricted to single symbol pairs as their centers (i.e. the left-hand sides of the rules). The solution handles also strings of symbol pairs (or regular expressions over the pair alphabet) as centers of two-level rules. Then, the treatment of context conditions is generalized with unions and relative complements etc. Moreover, an extended rule type, the presence requirement, combines the generalized context conditions with center conditions at both sides of the rules. The left-hand side specifies where the rule applies and the right-hand side specifies which of the applications are successful. The original two-level grammars were represented as a separate finite-state machine for each rule and the whole grammar as their intersection. The new methods are used first to redefine this setup, and then to implement a uniform conflict resolution scheme for all rules. The resolution scheme prefers successful and the longest embedded applications of rules, but it treats partially overlapping or explicitly independent applications of rules conjunctively. The composite rules of the original formalism have a marginal status in the new formalism because only identity pairs are allowed in locations where no rule is applicable.
9 schema:editor N64c608c755e047988b47a971fe689268
10 schema:genre chapter
11 schema:inLanguage en
12 schema:isAccessibleForFree false
13 schema:isPartOf N5ece8d623084404f834dded70e4063b5
14 schema:name Compiling Generalized Two-Level Rules and Grammars
15 schema:pagination 174-185
16 schema:productId N24e97ad7002b451a9f7ea4809accc18c
17 N29818e77357b48f48ed22515e9caa5e7
18 Nc07f43af5c1342208c985369a5b27134
19 schema:publisher Nb6b26013548b4e03907bf4cb5a123ad1
20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039928418
21 https://doi.org/10.1007/11816508_19
22 schema:sdDatePublished 2019-04-16T07:29
23 schema:sdLicense https://scigraph.springernature.com/explorer/license/
24 schema:sdPublisher N6459ec2122704dc69de1c70ce58e079c
25 schema:url https://link.springer.com/10.1007%2F11816508_19
26 sgo:license sg:explorer/license/
27 sgo:sdDataset chapters
28 rdf:type schema:Chapter
29 N24e97ad7002b451a9f7ea4809accc18c schema:name doi
30 schema:value 10.1007/11816508_19
31 rdf:type schema:PropertyValue
32 N29818e77357b48f48ed22515e9caa5e7 schema:name dimensions_id
33 schema:value pub.1039928418
34 rdf:type schema:PropertyValue
35 N2fc129a29ebd4f7aa28d14d86e5a7aa0 schema:familyName Pahikkala
36 schema:givenName Tapio
37 rdf:type schema:Person
38 N44837577326a46808ea8be3406e70227 schema:familyName Salakoski
39 schema:givenName Tapio
40 rdf:type schema:Person
41 N4a8ab7c1e6e64496825922c2f1f47a12 rdf:first N2fc129a29ebd4f7aa28d14d86e5a7aa0
42 rdf:rest rdf:nil
43 N5ece8d623084404f834dded70e4063b5 schema:isbn 978-3-540-37334-6
44 978-3-540-37336-0
45 schema:name Advances in Natural Language Processing
46 rdf:type schema:Book
47 N6459ec2122704dc69de1c70ce58e079c schema:name Springer Nature - SN SciGraph project
48 rdf:type schema:Organization
49 N64c608c755e047988b47a971fe689268 rdf:first N44837577326a46808ea8be3406e70227
50 rdf:rest N7fd7f0f7428b42c98eb28a8994f2c2cd
51 N6c9ab1124a3d4091a104d0f2f60bf1e3 schema:familyName Pyysalo
52 schema:givenName Sampo
53 rdf:type schema:Person
54 N7fd7f0f7428b42c98eb28a8994f2c2cd rdf:first Nc14590f9460f405dace98fc1bea1dfce
55 rdf:rest Ne23f5e3f2d3e446ea3424583938bbd16
56 Nb6b26013548b4e03907bf4cb5a123ad1 schema:location Berlin, Heidelberg
57 schema:name Springer Berlin Heidelberg
58 rdf:type schema:Organisation
59 Nb7099e1e7b454f22a693121c879a6f2b rdf:first sg:person.01066210767.64
60 rdf:rest Nd9245d90ce174e5599e5a45354bfffc3
61 Nc07f43af5c1342208c985369a5b27134 schema:name readcube_id
62 schema:value be340229b3f3f0257fb14756e09b9aaab1b7be386345d5a5e1992e7895f43c1e
63 rdf:type schema:PropertyValue
64 Nc14590f9460f405dace98fc1bea1dfce schema:familyName Ginter
65 schema:givenName Filip
66 rdf:type schema:Person
67 Nd9245d90ce174e5599e5a45354bfffc3 rdf:first sg:person.014251223113.28
68 rdf:rest rdf:nil
69 Ne23f5e3f2d3e446ea3424583938bbd16 rdf:first N6c9ab1124a3d4091a104d0f2f60bf1e3
70 rdf:rest N4a8ab7c1e6e64496825922c2f1f47a12
71 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
72 schema:name Information and Computing Sciences
73 rdf:type schema:DefinedTerm
74 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
75 schema:name Computation Theory and Mathematics
76 rdf:type schema:DefinedTerm
77 sg:person.01066210767.64 schema:affiliation https://www.grid.ac/institutes/grid.7737.4
78 schema:familyName Yli-Jyrä
79 schema:givenName Anssi
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01066210767.64
81 rdf:type schema:Person
82 sg:person.014251223113.28 schema:affiliation https://www.grid.ac/institutes/grid.7737.4
83 schema:familyName Koskenniemi
84 schema:givenName Kimmo
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014251223113.28
86 rdf:type schema:Person
87 https://doi.org/10.3115/991365.991445 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021646659
88 rdf:type schema:CreativeWork
89 https://doi.org/10.3115/993268.993277 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048349603
90 rdf:type schema:CreativeWork
91 https://www.grid.ac/institutes/grid.7737.4 schema:alternateName University of Helsinki
92 schema:name Department of General Linguistics, University of Helsinki, Finland
93 Language Bank Service, CSC Scientific Computing Ltd., Finland
94 rdf:type schema:Organization
 




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


...