String Languages Generated by Total Deterministic Macro Tree Transducers View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1999

AUTHORS

Sebastian Maneth

ABSTRACT

The class of string languages obtained by taking the yields of output tree languages of total deterministic macro tree transducers (MTTs) is investigated. The first main result is that MTTs which are linear and nondeleting in the parameters generate the same class of string languages as total deterministic top-down tree transducers. The second main result is a so called “bridge theorem”; it can be used to show that there is a string language generated by a nondeterministic top-down tree transducer with monadic input, i.e., an ET0L language, which cannot be generated by an MTT. In fact, it is shown that this language cannot even be generated by the composition closure of MTTs; hence it is also not in the IO-hierarchy. More... »

PAGES

258-272

Book

TITLE

Foundations of Software Science and Computation Structures

ISBN

978-3-540-65719-4
978-3-540-49019-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-49019-1_18

DOI

http://dx.doi.org/10.1007/3-540-49019-1_18

DIMENSIONS

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


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/20", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Language, Communication and Culture", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/2004", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Linguistics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Leiden University, PO Box 9512, 2300, RA Leiden, The Netherlands", 
          "id": "http://www.grid.ac/institutes/grid.5132.5", 
          "name": [
            "Department of Computer Science, Leiden University, PO Box 9512, 2300, RA Leiden, The Netherlands"
          ], 
          "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"
      }
    ], 
    "datePublished": "1999", 
    "datePublishedReg": "1999-01-01", 
    "description": "The class of string languages obtained by taking the yields of output tree languages of total deterministic macro tree transducers (MTTs) is investigated. The first main result is that MTTs which are linear and nondeleting in the parameters generate the same class of string languages as total deterministic top-down tree transducers. The second main result is a so called \u201cbridge theorem\u201d; it can be used to show that there is a string language generated by a nondeterministic top-down tree transducer with monadic input, i.e., an ET0L language, which cannot be generated by an MTT. In fact, it is shown that this language cannot even be generated by the composition closure of MTTs; hence it is also not in the IO-hierarchy.", 
    "editor": [
      {
        "familyName": "Thomas", 
        "givenName": "Wolfgang", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-49019-1_18", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-65719-4", 
        "978-3-540-49019-7"
      ], 
      "name": "Foundations of Software Science and Computation Structures", 
      "type": "Book"
    }, 
    "keywords": [
      "deterministic macro tree transducers", 
      "string languages", 
      "macro tree transducers", 
      "tree transducers", 
      "ET0L languages", 
      "tree languages", 
      "language", 
      "composition closure", 
      "bridge theorem", 
      "nondeleting", 
      "class", 
      "fact", 
      "second main result", 
      "same class", 
      "first main result", 
      "input", 
      "main results", 
      "closure", 
      "results", 
      "theorem", 
      "transducer", 
      "parameters", 
      "yield", 
      "output tree languages", 
      "total deterministic macro tree transducers", 
      "monadic input", 
      "IO-hierarchy"
    ], 
    "name": "String Languages Generated by Total Deterministic Macro Tree Transducers", 
    "pagination": "258-272", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009144053"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-49019-1_18"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-49019-1_18", 
      "https://app.dimensions.ai/details/publication/pub.1009144053"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:47", 
    "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_140.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-49019-1_18"
  }
]
 

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/3-540-49019-1_18'

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/3-540-49019-1_18'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-49019-1_18'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-49019-1_18'


 

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

87 TRIPLES      23 PREDICATES      53 URIs      46 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-49019-1_18 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author N256339077c86401390ef6af92a639651
4 schema:datePublished 1999
5 schema:datePublishedReg 1999-01-01
6 schema:description The class of string languages obtained by taking the yields of output tree languages of total deterministic macro tree transducers (MTTs) is investigated. The first main result is that MTTs which are linear and nondeleting in the parameters generate the same class of string languages as total deterministic top-down tree transducers. The second main result is a so called “bridge theorem”; it can be used to show that there is a string language generated by a nondeterministic top-down tree transducer with monadic input, i.e., an ET0L language, which cannot be generated by an MTT. In fact, it is shown that this language cannot even be generated by the composition closure of MTTs; hence it is also not in the IO-hierarchy.
7 schema:editor N3d57b5706d854be79382169fc4431899
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N0906fd2a87964912bc5d7bcae4fa63ad
12 schema:keywords ET0L languages
13 IO-hierarchy
14 bridge theorem
15 class
16 closure
17 composition closure
18 deterministic macro tree transducers
19 fact
20 first main result
21 input
22 language
23 macro tree transducers
24 main results
25 monadic input
26 nondeleting
27 output tree languages
28 parameters
29 results
30 same class
31 second main result
32 string languages
33 theorem
34 total deterministic macro tree transducers
35 transducer
36 tree languages
37 tree transducers
38 yield
39 schema:name String Languages Generated by Total Deterministic Macro Tree Transducers
40 schema:pagination 258-272
41 schema:productId N20a5f2e1e6a24f28bb881299595bb65e
42 N6578405a12db4ae98be619c7b326e383
43 schema:publisher N9ab898da072c496ca6c518560a9b3da7
44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009144053
45 https://doi.org/10.1007/3-540-49019-1_18
46 schema:sdDatePublished 2021-11-01T18:47
47 schema:sdLicense https://scigraph.springernature.com/explorer/license/
48 schema:sdPublisher N1021a5f285074e9bbbc0fdf78744920a
49 schema:url https://doi.org/10.1007/3-540-49019-1_18
50 sgo:license sg:explorer/license/
51 sgo:sdDataset chapters
52 rdf:type schema:Chapter
53 N01e894a0ec914d56bf21cbf15facef49 schema:familyName Thomas
54 schema:givenName Wolfgang
55 rdf:type schema:Person
56 N0906fd2a87964912bc5d7bcae4fa63ad schema:isbn 978-3-540-49019-7
57 978-3-540-65719-4
58 schema:name Foundations of Software Science and Computation Structures
59 rdf:type schema:Book
60 N1021a5f285074e9bbbc0fdf78744920a schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 N20a5f2e1e6a24f28bb881299595bb65e schema:name dimensions_id
63 schema:value pub.1009144053
64 rdf:type schema:PropertyValue
65 N256339077c86401390ef6af92a639651 rdf:first sg:person.016240662443.33
66 rdf:rest rdf:nil
67 N3d57b5706d854be79382169fc4431899 rdf:first N01e894a0ec914d56bf21cbf15facef49
68 rdf:rest rdf:nil
69 N6578405a12db4ae98be619c7b326e383 schema:name doi
70 schema:value 10.1007/3-540-49019-1_18
71 rdf:type schema:PropertyValue
72 N9ab898da072c496ca6c518560a9b3da7 schema:name Springer Nature
73 rdf:type schema:Organisation
74 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
75 schema:name Language, Communication and Culture
76 rdf:type schema:DefinedTerm
77 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
78 schema:name Linguistics
79 rdf:type schema:DefinedTerm
80 sg:person.016240662443.33 schema:affiliation grid-institutes:grid.5132.5
81 schema:familyName Maneth
82 schema:givenName Sebastian
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016240662443.33
84 rdf:type schema:Person
85 grid-institutes:grid.5132.5 schema:alternateName Department of Computer Science, Leiden University, PO Box 9512, 2300, RA Leiden, The Netherlands
86 schema:name Department of Computer Science, Leiden University, PO Box 9512, 2300, RA Leiden, The Netherlands
87 rdf:type schema:Organization
 




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


...