About: Tree (automata theory)     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon
http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FTree_%28automata_theory%29&invfp=IFP_OFF&sas=SAME_AS_OFF

In automata theory, a tree is a particular way of representing a tree structure as sequences of natural numbers. For example, each node of the tree is a word over set of natural numbers, which helps this definition to be used in automata theory. A tree is called ordered if there is an order among the successors of each of its nodes. The above definition of tree naturally suggests an order among the successors, which can be used to make the tree ranked. For example, the above definition is used in the definition of an infinite tree automaton.

AttributesValues
rdfs:label
  • Tree (automata theory) (en)
rdfs:comment
  • In automata theory, a tree is a particular way of representing a tree structure as sequences of natural numbers. For example, each node of the tree is a word over set of natural numbers, which helps this definition to be used in automata theory. A tree is called ordered if there is an order among the successors of each of its nodes. The above definition of tree naturally suggests an order among the successors, which can be used to make the tree ranked. For example, the above definition is used in the definition of an infinite tree automaton. (en)
foaf:depiction
  • http://commons.wikimedia.org/wiki/Special:FilePath/An_example_of_infinite_tree_structure.png
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
sameAs
dbp:wikiPageUsesTemplate
thumbnail
has abstract
  • In automata theory, a tree is a particular way of representing a tree structure as sequences of natural numbers. For example, each node of the tree is a word over set of natural numbers, which helps this definition to be used in automata theory. A tree is a set T ⊆ * such that if t.c ∈ T, with t ∈ * and c ∈ , then t ∈ T and t.c1 ∈ T for all 0 ≤ c1 < c. The elements of T are known as nodes, and the empty word ε is the (single) root of T. For every t ∈ T, the element t.c ∈ T is a successor of t in direction c. The number of successors of t is called its degree or arity, and represented as d(t). A node is a leaf if it has no successors. If every node of a tree has finitely many successors, then it is called a finitely, otherwise an infinitely branching tree. A path π is a subset of T such that ε ∈ π and for every t ∈ T, either t is a leaf or there exists a unique c ∈ such that t.c ∈ π. A path may be a finite or infinite set. If all paths of a tree are finite then the tree is called finite, otherwise infinite. A tree is called fully infinite if all its paths are infinite. Given an alphabet Σ, a Σ-labeled tree is a pair (T,V), where T is a tree and V: T → Σ maps each node of T to a symbol in Σ. A labeled tree formally defines a commonly used term tree structure. A set of labeled trees is called a tree language. A tree is called ordered if there is an order among the successors of each of its nodes. The above definition of tree naturally suggests an order among the successors, which can be used to make the tree ranked. In the case of ranked alphabets, an extra function Ar: Σ → is defined. This function associates a fixed arity to each symbol of the alphabet. In this case, each t ∈ T has to satisfy Ar(V(t)) = d(t). The trees that satisfy this property are called ranked trees. The trees that do not (necessarily) satisfy that property are called unranked. For example, the above definition is used in the definition of an infinite tree automaton. (en)
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is Wikipage disambiguates of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git139 as of Feb 29 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 67 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software