Syntax-Directed Translations and Quasi-alphabetic Tree Bimorphisms — Revisited View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2009

AUTHORS

Andreas Maletti , Cătălin Ionuţ Tîrnăucă

ABSTRACT

Quasi-alphabetic tree bimorphisms [Steinby, Tîrnăucă: Defining syntax-directed translations by tree bimorphisms. Theor. Comput. Sci., to appear. http://dx.doi.org/10.1016/j.tcs.2009.03.009, 2009] are reconsidered. It is known that the class of (string) translations defined by such bimorphisms coincides with the class of syntax-directed translations. This result is extended to a smaller class of tree bimorphisms namely (linear and complete) symbol-to-symbol tree bimorphisms. Moreover, it is shown that the class of simple syntax-directed translations coincides with the class of translations defined by alphabetic tree bimorphisms (also known as finite-state relabelings). This proves that alphabetic tree bimorphisms are not sufficiently powerful to model all syntax-directed translations. Finally, it is shown that the class of tree transformations defined by quasi-alphabetic tree bimorphisms is closed under composition. The corresponding result is known in the variable-free case. Overall, the main results of [Steinby, Tîrnăucă] are strengthened. More... »

PAGES

305-317

Book

TITLE

Algebraic Informatics

ISBN

978-3-642-03563-0
978-3-642-03564-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-03564-7_20

DOI

http://dx.doi.org/10.1007/978-3-642-03564-7_20

DIMENSIONS

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


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": "Departament de Filologies Rom\u00e0niques, Universitat Rovira i Virgili, Av. Catalunya\u00a035, 43002, Tarragona, Spain", 
          "id": "http://www.grid.ac/institutes/grid.410367.7", 
          "name": [
            "Departament de Filologies Rom\u00e0niques, Universitat Rovira i Virgili, Av. Catalunya\u00a035, 43002, Tarragona, Spain"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Maletti", 
        "givenName": "Andreas", 
        "id": "sg:person.016645332751.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645332751.01"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Departament de Filologies Rom\u00e0niques, Universitat Rovira i Virgili, Av. Catalunya\u00a035, 43002, Tarragona, Spain", 
          "id": "http://www.grid.ac/institutes/grid.410367.7", 
          "name": [
            "Departament de Filologies Rom\u00e0niques, Universitat Rovira i Virgili, Av. Catalunya\u00a035, 43002, Tarragona, Spain"
          ], 
          "type": "Organization"
        }, 
        "familyName": "T\u00eern\u0103uc\u0103", 
        "givenName": "C\u0103t\u0103lin Ionu\u0163", 
        "id": "sg:person.012060073575.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012060073575.03"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "Quasi-alphabetic tree bimorphisms [Steinby, T\u00eern\u0103uc\u0103: Defining syntax-directed translations by tree bimorphisms. Theor. Comput. Sci., to appear. http://dx.doi.org/10.1016/j.tcs.2009.03.009, 2009] are reconsidered. It is known that the class of (string) translations defined by such bimorphisms coincides with the class of syntax-directed translations. This result is extended to a smaller class of tree bimorphisms namely (linear and complete) symbol-to-symbol tree bimorphisms. Moreover, it is shown that the class of simple syntax-directed translations coincides with the class of translations defined by alphabetic tree bimorphisms (also known as finite-state relabelings). This proves that alphabetic tree bimorphisms are not sufficiently powerful to model all syntax-directed translations. Finally, it is shown that the class of tree transformations defined by quasi-alphabetic tree bimorphisms is closed under composition. The corresponding result is known in the variable-free case. Overall, the main results of [Steinby, T\u00eern\u0103uc\u0103] are strengthened.", 
    "editor": [
      {
        "familyName": "Bozapalidis", 
        "givenName": "Symeon", 
        "type": "Person"
      }, 
      {
        "familyName": "Rahonis", 
        "givenName": "George", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-03564-7_20", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-03563-0", 
        "978-3-642-03564-7"
      ], 
      "name": "Algebraic Informatics", 
      "type": "Book"
    }, 
    "keywords": [
      "translation", 
      "results", 
      "cases", 
      "main results", 
      "class", 
      "trees", 
      "coincide", 
      "syntax-directed translation", 
      "small class", 
      "bimorphism", 
      "transformation", 
      "composition", 
      "corresponding results", 
      "symbols", 
      "alphabetic trees", 
      "tree transformations", 
      "Quasi-alphabetic tree", 
      "class of translations", 
      "such bimorphisms coincides", 
      "bimorphisms coincides", 
      "symbol tree bimorphisms", 
      "tree bimorphisms", 
      "simple syntax-directed translations coincides", 
      "syntax-directed translations coincides", 
      "translations coincides", 
      "alphabetic tree bimorphisms", 
      "quasi-alphabetic tree bimorphisms", 
      "variable-free case"
    ], 
    "name": "Syntax-Directed Translations and Quasi-alphabetic Tree Bimorphisms \u2014 Revisited", 
    "pagination": "305-317", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1002506571"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-03564-7_20"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-03564-7_20", 
      "https://app.dimensions.ai/details/publication/pub.1002506571"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:12", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_57.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-03564-7_20"
  }
]
 

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-03564-7_20'

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-03564-7_20'

Turtle is a human-readable linked data format.

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

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-03564-7_20'


 

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

100 TRIPLES      23 PREDICATES      54 URIs      47 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-03564-7_20 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N3a39d405440147b398b6862fd790b63a
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description Quasi-alphabetic tree bimorphisms [Steinby, Tîrnăucă: Defining syntax-directed translations by tree bimorphisms. Theor. Comput. Sci., to appear. http://dx.doi.org/10.1016/j.tcs.2009.03.009, 2009] are reconsidered. It is known that the class of (string) translations defined by such bimorphisms coincides with the class of syntax-directed translations. This result is extended to a smaller class of tree bimorphisms namely (linear and complete) symbol-to-symbol tree bimorphisms. Moreover, it is shown that the class of simple syntax-directed translations coincides with the class of translations defined by alphabetic tree bimorphisms (also known as finite-state relabelings). This proves that alphabetic tree bimorphisms are not sufficiently powerful to model all syntax-directed translations. Finally, it is shown that the class of tree transformations defined by quasi-alphabetic tree bimorphisms is closed under composition. The corresponding result is known in the variable-free case. Overall, the main results of [Steinby, Tîrnăucă] are strengthened.
7 schema:editor N3cdbc8bcf4cf422280575886c5c48fde
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N9b6c35ee4f024b479b862e4e293223e3
12 schema:keywords Quasi-alphabetic tree
13 alphabetic tree bimorphisms
14 alphabetic trees
15 bimorphism
16 bimorphisms coincides
17 cases
18 class
19 class of translations
20 coincide
21 composition
22 corresponding results
23 main results
24 quasi-alphabetic tree bimorphisms
25 results
26 simple syntax-directed translations coincides
27 small class
28 such bimorphisms coincides
29 symbol tree bimorphisms
30 symbols
31 syntax-directed translation
32 syntax-directed translations coincides
33 transformation
34 translation
35 translations coincides
36 tree bimorphisms
37 tree transformations
38 trees
39 variable-free case
40 schema:name Syntax-Directed Translations and Quasi-alphabetic Tree Bimorphisms — Revisited
41 schema:pagination 305-317
42 schema:productId N46d07e4deaa3452cb4564ee05c6de339
43 N55bfb31885ce4abaaee19bb7e4bf02b0
44 schema:publisher Nd333359c6c9d4d42970a52689daabd94
45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002506571
46 https://doi.org/10.1007/978-3-642-03564-7_20
47 schema:sdDatePublished 2021-12-01T20:12
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher Nc31e6746bbe2416fbd506d8d591599b1
50 schema:url https://doi.org/10.1007/978-3-642-03564-7_20
51 sgo:license sg:explorer/license/
52 sgo:sdDataset chapters
53 rdf:type schema:Chapter
54 N1cd26447a4c7420b84f03f87af82614e rdf:first sg:person.012060073575.03
55 rdf:rest rdf:nil
56 N3a39d405440147b398b6862fd790b63a rdf:first sg:person.016645332751.01
57 rdf:rest N1cd26447a4c7420b84f03f87af82614e
58 N3cdbc8bcf4cf422280575886c5c48fde rdf:first N754077113c1d4a6d870ca5828c1e3a40
59 rdf:rest N92e26809af99441982d3c2ef03b9e593
60 N3f05af210fb94a3d906aeeb719c3414f schema:familyName Rahonis
61 schema:givenName George
62 rdf:type schema:Person
63 N46d07e4deaa3452cb4564ee05c6de339 schema:name doi
64 schema:value 10.1007/978-3-642-03564-7_20
65 rdf:type schema:PropertyValue
66 N55bfb31885ce4abaaee19bb7e4bf02b0 schema:name dimensions_id
67 schema:value pub.1002506571
68 rdf:type schema:PropertyValue
69 N754077113c1d4a6d870ca5828c1e3a40 schema:familyName Bozapalidis
70 schema:givenName Symeon
71 rdf:type schema:Person
72 N92e26809af99441982d3c2ef03b9e593 rdf:first N3f05af210fb94a3d906aeeb719c3414f
73 rdf:rest rdf:nil
74 N9b6c35ee4f024b479b862e4e293223e3 schema:isbn 978-3-642-03563-0
75 978-3-642-03564-7
76 schema:name Algebraic Informatics
77 rdf:type schema:Book
78 Nc31e6746bbe2416fbd506d8d591599b1 schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 Nd333359c6c9d4d42970a52689daabd94 schema:name Springer Nature
81 rdf:type schema:Organisation
82 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
83 schema:name Mathematical Sciences
84 rdf:type schema:DefinedTerm
85 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
86 schema:name Pure Mathematics
87 rdf:type schema:DefinedTerm
88 sg:person.012060073575.03 schema:affiliation grid-institutes:grid.410367.7
89 schema:familyName Tîrnăucă
90 schema:givenName Cătălin Ionuţ
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012060073575.03
92 rdf:type schema:Person
93 sg:person.016645332751.01 schema:affiliation grid-institutes:grid.410367.7
94 schema:familyName Maletti
95 schema:givenName Andreas
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645332751.01
97 rdf:type schema:Person
98 grid-institutes:grid.410367.7 schema:alternateName Departament de Filologies Romàniques, Universitat Rovira i Virgili, Av. Catalunya 35, 43002, Tarragona, Spain
99 schema:name Departament de Filologies Romàniques, Universitat Rovira i Virgili, Av. Catalunya 35, 43002, Tarragona, Spain
100 rdf:type schema:Organization
 




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


...