Myhill-Nerode Theorem for Recognizable Tree Series Revisited View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2008-01-01

AUTHORS

Andreas Maletti

ABSTRACT

In this contribution the Myhill-Nerode congruence relation on tree series is reviewed and a more detailed analysis of its properties is presented. It is shown that, if a tree series is deterministically recognizable over a zero-divisor free and commutative semiring, then the Myhill-Nerode congruence relation has finite index. By [Borchardt: Myhill-Nerode Theorem for Recognizable Tree Series. LNCS 2710. Springer 2003] the converse holds for commutative semifields, but not in general. In the second part, a slightly adapted version of the Myhill-Nerode congruence relation is defined and a characterization is obtained for all-accepting weighted tree automata over multiplicatively cancellative and commutative semirings. More... »

PAGES

106-120

Book

TITLE

LATIN 2008: Theoretical Informatics

ISBN

978-3-540-78772-3
978-3-540-78773-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-78773-0_10

DOI

http://dx.doi.org/10.1007/978-3-540-78773-0_10

DIMENSIONS

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


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": "International Computer Science Institute, 1947 Center Street, Suite 600, CA 94704, Berkeley, USA", 
          "id": "http://www.grid.ac/institutes/grid.185107.a", 
          "name": [
            "International Computer Science Institute, 1947 Center Street, Suite 600, CA 94704, Berkeley, USA"
          ], 
          "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"
      }
    ], 
    "datePublished": "2008-01-01", 
    "datePublishedReg": "2008-01-01", 
    "description": "In this contribution the Myhill-Nerode congruence relation on tree series is reviewed and a more detailed analysis of its properties is presented. It is shown that, if a tree series is deterministically recognizable over a zero-divisor free and commutative semiring, then the Myhill-Nerode congruence relation has finite index. By [Borchardt: Myhill-Nerode Theorem for Recognizable Tree Series. LNCS\u00a02710. Springer 2003] the converse holds for commutative semifields, but not in general. In the second part, a slightly adapted version of the Myhill-Nerode congruence relation is defined and a characterization is obtained for all-accepting weighted tree automata over multiplicatively cancellative and commutative semirings.", 
    "editor": [
      {
        "familyName": "Laber", 
        "givenName": "Eduardo Sany", 
        "type": "Person"
      }, 
      {
        "familyName": "Bornstein", 
        "givenName": "Claudson", 
        "type": "Person"
      }, 
      {
        "familyName": "Nogueira", 
        "givenName": "Loana Tito", 
        "type": "Person"
      }, 
      {
        "familyName": "Faria", 
        "givenName": "Luerbio", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-78773-0_10", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-78772-3", 
        "978-3-540-78773-0"
      ], 
      "name": "LATIN 2008: Theoretical Informatics", 
      "type": "Book"
    }, 
    "keywords": [
      "contribution", 
      "congruence relations", 
      "relation", 
      "tree series", 
      "series", 
      "detailed analysis", 
      "analysis", 
      "properties", 
      "zero-divisors", 
      "commutative semirings", 
      "semirings", 
      "finite index", 
      "index", 
      "converse", 
      "commutative semifields", 
      "semifields", 
      "second part", 
      "part", 
      "version", 
      "characterization", 
      "automata", 
      "Myhill-Nerode theorem", 
      "theorem", 
      "Revisited", 
      "Myhill-Nerode congruence relation", 
      "tree automata", 
      "Recognizable Tree Series Revisited", 
      "Tree Series Revisited", 
      "Series Revisited"
    ], 
    "name": "Myhill-Nerode Theorem for Recognizable Tree Series Revisited", 
    "pagination": "106-120", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1008898111"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-78773-0_10"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-78773-0_10", 
      "https://app.dimensions.ai/details/publication/pub.1008898111"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:06", 
    "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_344.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-78773-0_10"
  }
]
 

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-78773-0_10'

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-78773-0_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-78773-0_10'

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-78773-0_10'


 

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

104 TRIPLES      23 PREDICATES      54 URIs      47 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-78773-0_10 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N5b6c26d3762742deaaedf2177504a60c
4 schema:datePublished 2008-01-01
5 schema:datePublishedReg 2008-01-01
6 schema:description In this contribution the Myhill-Nerode congruence relation on tree series is reviewed and a more detailed analysis of its properties is presented. It is shown that, if a tree series is deterministically recognizable over a zero-divisor free and commutative semiring, then the Myhill-Nerode congruence relation has finite index. By [Borchardt: Myhill-Nerode Theorem for Recognizable Tree Series. LNCS 2710. Springer 2003] the converse holds for commutative semifields, but not in general. In the second part, a slightly adapted version of the Myhill-Nerode congruence relation is defined and a characterization is obtained for all-accepting weighted tree automata over multiplicatively cancellative and commutative semirings.
7 schema:editor N447c6af49b6b4bddaff49cfa3db87955
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Ne7a823e4cc0945c39149700035c241bc
12 schema:keywords Myhill-Nerode congruence relation
13 Myhill-Nerode theorem
14 Recognizable Tree Series Revisited
15 Revisited
16 Series Revisited
17 Tree Series Revisited
18 analysis
19 automata
20 characterization
21 commutative semifields
22 commutative semirings
23 congruence relations
24 contribution
25 converse
26 detailed analysis
27 finite index
28 index
29 part
30 properties
31 relation
32 second part
33 semifields
34 semirings
35 series
36 theorem
37 tree automata
38 tree series
39 version
40 zero-divisors
41 schema:name Myhill-Nerode Theorem for Recognizable Tree Series Revisited
42 schema:pagination 106-120
43 schema:productId Nb5813644d37242d48934f84e95346355
44 Ncdf56a62524f40769c84560138274dd5
45 schema:publisher Nc7178e8ab0624099adb501edea7894a5
46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008898111
47 https://doi.org/10.1007/978-3-540-78773-0_10
48 schema:sdDatePublished 2021-12-01T20:06
49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
50 schema:sdPublisher Ne338add067b244c9ba104a7aa1ef5fd1
51 schema:url https://doi.org/10.1007/978-3-540-78773-0_10
52 sgo:license sg:explorer/license/
53 sgo:sdDataset chapters
54 rdf:type schema:Chapter
55 N447c6af49b6b4bddaff49cfa3db87955 rdf:first Ndfbab68aebfa404998f7e54e85052a7c
56 rdf:rest Nda0cec4cf1f342ada90dbcf108f3d1c2
57 N5b6c26d3762742deaaedf2177504a60c rdf:first sg:person.016645332751.01
58 rdf:rest rdf:nil
59 Nb5813644d37242d48934f84e95346355 schema:name dimensions_id
60 schema:value pub.1008898111
61 rdf:type schema:PropertyValue
62 Nbdaebad64d004e10ab79827a27ca635e rdf:first Nf80879c2b53a46bfa6a4b58085c350c9
63 rdf:rest Nf89f37602db648b3b815a76539a2c9b5
64 Nc7178e8ab0624099adb501edea7894a5 schema:name Springer Nature
65 rdf:type schema:Organisation
66 Ncdf56a62524f40769c84560138274dd5 schema:name doi
67 schema:value 10.1007/978-3-540-78773-0_10
68 rdf:type schema:PropertyValue
69 Nda0cec4cf1f342ada90dbcf108f3d1c2 rdf:first Ne7935f04847e40b0b067ea4254c548bd
70 rdf:rest Nbdaebad64d004e10ab79827a27ca635e
71 Ndfbab68aebfa404998f7e54e85052a7c schema:familyName Laber
72 schema:givenName Eduardo Sany
73 rdf:type schema:Person
74 Ne338add067b244c9ba104a7aa1ef5fd1 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 Ne7935f04847e40b0b067ea4254c548bd schema:familyName Bornstein
77 schema:givenName Claudson
78 rdf:type schema:Person
79 Ne7a823e4cc0945c39149700035c241bc schema:isbn 978-3-540-78772-3
80 978-3-540-78773-0
81 schema:name LATIN 2008: Theoretical Informatics
82 rdf:type schema:Book
83 Nf80879c2b53a46bfa6a4b58085c350c9 schema:familyName Nogueira
84 schema:givenName Loana Tito
85 rdf:type schema:Person
86 Nf89f37602db648b3b815a76539a2c9b5 rdf:first Nfa076996b5ea4862b8da0b00e3bc52ef
87 rdf:rest rdf:nil
88 Nfa076996b5ea4862b8da0b00e3bc52ef schema:familyName Faria
89 schema:givenName Luerbio
90 rdf:type schema:Person
91 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
92 schema:name Mathematical Sciences
93 rdf:type schema:DefinedTerm
94 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
95 schema:name Pure Mathematics
96 rdf:type schema:DefinedTerm
97 sg:person.016645332751.01 schema:affiliation grid-institutes:grid.185107.a
98 schema:familyName Maletti
99 schema:givenName Andreas
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645332751.01
101 rdf:type schema:Person
102 grid-institutes:grid.185107.a schema:alternateName International Computer Science Institute, 1947 Center Street, Suite 600, CA 94704, Berkeley, USA
103 schema:name International Computer Science Institute, 1947 Center Street, Suite 600, CA 94704, Berkeley, USA
104 rdf:type schema:Organization
 




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


...