Tree Languages View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1997

AUTHORS

Ferenc Gécseg , Magnus Steinby

ABSTRACT

The theory of tree automata and tree languages emerged in the middle of the 1960s quite naturally from the view of finite automata as unary algebras advocated by J. R. Büchi and J. B. Wright. From this perspective the generalization from strings to trees means simply that any finite algebra of finite type can be regarded as an automaton which as inputs accepts terms over the ranked alphabet formed by the operation symbols of the algebra, and these terms again can be seen as (formal representations of) labeled trees with a left-to-right ordering of the branches. Strings over a finite alphabet can then be regarded as terms over a unary ranked alphabet, and hence finite automata become special tree automata and string languages unary tree languages. The theory of tree automata and tree languages can thus be seen as an outgrowth of Büchi’s and Wright’s program which had as its goal a general theory that would encompass automata, universal algebra, equational logic, and formal languages. Some interesting vistas of this program and its development are opened by Büchi’s posthumous book [Büc89] in which many of the ideas are traced back to people like Thue, Skolem, Post, and even Leibniz. More... »

PAGES

1-68

Book

TITLE

Handbook of Formal Languages

ISBN

978-3-642-63859-6
978-3-642-59126-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-59126-6_1

DOI

http://dx.doi.org/10.1007/978-3-642-59126-6_1

DIMENSIONS

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


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": [
      {
        "familyName": "G\u00e9cseg", 
        "givenName": "Ferenc", 
        "id": "sg:person.015415647207.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015415647207.63"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Steinby", 
        "givenName": "Magnus", 
        "id": "sg:person.015641324125.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015641324125.49"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1997", 
    "datePublishedReg": "1997-01-01", 
    "description": "The theory of tree automata and tree languages emerged in the middle of the 1960s quite naturally from the view of finite automata as unary algebras advocated by J. R. B\u00fcchi and J. B. Wright. From this perspective the generalization from strings to trees means simply that any finite algebra of finite type can be regarded as an automaton which as inputs accepts terms over the ranked alphabet formed by the operation symbols of the algebra, and these terms again can be seen as (formal representations of) labeled trees with a left-to-right ordering of the branches. Strings over a finite alphabet can then be regarded as terms over a unary ranked alphabet, and hence finite automata become special tree automata and string languages unary tree languages. The theory of tree automata and tree languages can thus be seen as an outgrowth of B\u00fcchi\u2019s and Wright\u2019s program which had as its goal a general theory that would encompass automata, universal algebra, equational logic, and formal languages. Some interesting vistas of this program and its development are opened by B\u00fcchi\u2019s posthumous book [B\u00fcc89] in which many of the ideas are traced back to people like Thue, Skolem, Post, and even Leibniz.", 
    "editor": [
      {
        "familyName": "Rozenberg", 
        "givenName": "Grzegorz", 
        "type": "Person"
      }, 
      {
        "familyName": "Salomaa", 
        "givenName": "Arto", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-59126-6_1", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-63859-6", 
        "978-3-642-59126-6"
      ], 
      "name": "Handbook of Formal Languages", 
      "type": "Book"
    }, 
    "keywords": [
      "tree languages", 
      "posthumous book", 
      "finite automata", 
      "tree automata", 
      "formal language", 
      "language", 
      "operation symbols", 
      "alphabet", 
      "right ordering", 
      "finite alphabet", 
      "B\u00fcchi", 
      "book", 
      "automata", 
      "symbols", 
      "theory", 
      "Wright", 
      "idea", 
      "perspective", 
      "vistas", 
      "people", 
      "Thue", 
      "Leibniz", 
      "terms", 
      "strings", 
      "general theory", 
      "view", 
      "logic", 
      "post", 
      "program", 
      "middle", 
      "goal", 
      "equational logic", 
      "development", 
      "generalization", 
      "input", 
      "branches", 
      "types", 
      "ordering", 
      "unary algebras", 
      "finite algebras", 
      "universal algebra", 
      "finite type", 
      "algebra", 
      "trees", 
      "Skolem", 
      "outgrowth", 
      "special tree automata", 
      "string languages unary tree languages", 
      "languages unary tree languages", 
      "unary tree languages", 
      "Wright\u2019s program", 
      "interesting vistas", 
      "B\u00fcchi\u2019s posthumous book"
    ], 
    "name": "Tree Languages", 
    "pagination": "1-68", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1000867424"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-59126-6_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-59126-6_1", 
      "https://app.dimensions.ai/details/publication/pub.1000867424"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:11", 
    "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_449.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-59126-6_1"
  }
]
 

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-59126-6_1'

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-59126-6_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-59126-6_1'

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-59126-6_1'


 

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

120 TRIPLES      23 PREDICATES      79 URIs      72 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-59126-6_1 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Ncd48bc20a7764befb9201851d841e2da
4 schema:datePublished 1997
5 schema:datePublishedReg 1997-01-01
6 schema:description The theory of tree automata and tree languages emerged in the middle of the 1960s quite naturally from the view of finite automata as unary algebras advocated by J. R. Büchi and J. B. Wright. From this perspective the generalization from strings to trees means simply that any finite algebra of finite type can be regarded as an automaton which as inputs accepts terms over the ranked alphabet formed by the operation symbols of the algebra, and these terms again can be seen as (formal representations of) labeled trees with a left-to-right ordering of the branches. Strings over a finite alphabet can then be regarded as terms over a unary ranked alphabet, and hence finite automata become special tree automata and string languages unary tree languages. The theory of tree automata and tree languages can thus be seen as an outgrowth of Büchi’s and Wright’s program which had as its goal a general theory that would encompass automata, universal algebra, equational logic, and formal languages. Some interesting vistas of this program and its development are opened by Büchi’s posthumous book [Büc89] in which many of the ideas are traced back to people like Thue, Skolem, Post, and even Leibniz.
7 schema:editor N78c63673c4ac478090523339c1e72654
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nf9f4724d87c1474da0dfa5a52243ba9f
12 schema:keywords Büchi
13 Büchi’s posthumous book
14 Leibniz
15 Skolem
16 Thue
17 Wright
18 Wright’s program
19 algebra
20 alphabet
21 automata
22 book
23 branches
24 development
25 equational logic
26 finite algebras
27 finite alphabet
28 finite automata
29 finite type
30 formal language
31 general theory
32 generalization
33 goal
34 idea
35 input
36 interesting vistas
37 language
38 languages unary tree languages
39 logic
40 middle
41 operation symbols
42 ordering
43 outgrowth
44 people
45 perspective
46 post
47 posthumous book
48 program
49 right ordering
50 special tree automata
51 string languages unary tree languages
52 strings
53 symbols
54 terms
55 theory
56 tree automata
57 tree languages
58 trees
59 types
60 unary algebras
61 unary tree languages
62 universal algebra
63 view
64 vistas
65 schema:name Tree Languages
66 schema:pagination 1-68
67 schema:productId N2937b346109040a0a1c3b8da5988c18f
68 N409c7fa5ffd644f9a2486900214b9d1b
69 schema:publisher N1c0f7151c2dd4c80b7ff923c630a2bf9
70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000867424
71 https://doi.org/10.1007/978-3-642-59126-6_1
72 schema:sdDatePublished 2021-12-01T20:11
73 schema:sdLicense https://scigraph.springernature.com/explorer/license/
74 schema:sdPublisher N0c78e909d6354e6fb66b0f909a3bc83a
75 schema:url https://doi.org/10.1007/978-3-642-59126-6_1
76 sgo:license sg:explorer/license/
77 sgo:sdDataset chapters
78 rdf:type schema:Chapter
79 N0c78e909d6354e6fb66b0f909a3bc83a schema:name Springer Nature - SN SciGraph project
80 rdf:type schema:Organization
81 N1c0f7151c2dd4c80b7ff923c630a2bf9 schema:name Springer Nature
82 rdf:type schema:Organisation
83 N2937b346109040a0a1c3b8da5988c18f schema:name doi
84 schema:value 10.1007/978-3-642-59126-6_1
85 rdf:type schema:PropertyValue
86 N2c154afaa4ce4c518c72e46594d0c979 rdf:first Naf2af89102334659aeb6b290a2dc5a3a
87 rdf:rest rdf:nil
88 N409c7fa5ffd644f9a2486900214b9d1b schema:name dimensions_id
89 schema:value pub.1000867424
90 rdf:type schema:PropertyValue
91 N78c63673c4ac478090523339c1e72654 rdf:first N87fe6784e0e445209ed81e4b3af760de
92 rdf:rest N2c154afaa4ce4c518c72e46594d0c979
93 N87fe6784e0e445209ed81e4b3af760de schema:familyName Rozenberg
94 schema:givenName Grzegorz
95 rdf:type schema:Person
96 Naf2af89102334659aeb6b290a2dc5a3a schema:familyName Salomaa
97 schema:givenName Arto
98 rdf:type schema:Person
99 Ncd48bc20a7764befb9201851d841e2da rdf:first sg:person.015415647207.63
100 rdf:rest Nd8918e2fcb684c19b4e179ae1b091c1c
101 Nd8918e2fcb684c19b4e179ae1b091c1c rdf:first sg:person.015641324125.49
102 rdf:rest rdf:nil
103 Nf9f4724d87c1474da0dfa5a52243ba9f schema:isbn 978-3-642-59126-6
104 978-3-642-63859-6
105 schema:name Handbook of Formal Languages
106 rdf:type schema:Book
107 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
108 schema:name Mathematical Sciences
109 rdf:type schema:DefinedTerm
110 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
111 schema:name Pure Mathematics
112 rdf:type schema:DefinedTerm
113 sg:person.015415647207.63 schema:familyName Gécseg
114 schema:givenName Ferenc
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015415647207.63
116 rdf:type schema:Person
117 sg:person.015641324125.49 schema:familyName Steinby
118 schema:givenName Magnus
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015641324125.49
120 rdf:type schema:Person
 




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


...