Tree automaton (original) (raw)
En informatique théorique, plus précisément en théorie des langages, un automate d'arbre est une machine à états qui prend en entrée un arbre, plutôt qu'une chaîne de caractères pour les automates plus conventionnels, comme les automates finis.
| Property | Value |
|---|---|
| dbo:abstract | En informatique théorique, plus précisément en théorie des langages, un automate d'arbre est une machine à états qui prend en entrée un arbre, plutôt qu'une chaîne de caractères pour les automates plus conventionnels, comme les automates finis. (fr) A tree automaton is a type of state machine. Tree automata deal with tree structures, rather than the strings of more conventional state machines. The following article deals with branching tree automata, which correspond to regular languages of trees. As with classical automata, finite tree automata (FTA) can be either a deterministic automaton or not. According to how the automaton processes the input tree, finite tree automata can be of two types: (a) bottom up, (b) top down. This is an important issue, as although non-deterministic (ND) top-down and ND bottom-up tree automata are equivalent in expressive power, deterministic top-down automata are strictly less powerful than their deterministic bottom-up counterparts, because tree properties specified by deterministic top-down tree automata can only depend on path properties. (Deterministic bottom-up tree automata are as powerful as ND tree automata.) (en) Um autómato de árvore é um tipo de máquina de estados que lida com estruturas em árvore (de topologia em árvore), ao invés de strings como as máquinas de estado mais convencionais. Tal como acontece com os autómatos clássicos, um autómato de árvores finito (FTA) pode ser um autómato determinístico ou não. De acordo com a maneira que o autómato processa a árvore de entrada, o autómato de árvores finito pode ser de dois tipos: (a) bottom-up, (b) top-down. Essa é uma questão importante, pois apesar de os autómatos finitos de árvore não-determinísticos bottom-up e top-down serem equivalentes em poder expressivo, os autómatos determinísticos top-down são estritamente menos poderosos do que seus homólogos em bottom-up, por que as propriedades especificadas pelo autómato de árvores determinístico dependem apenas das propriedades do caminho. (Autómatos de árvore determinísticos bottom-up são tão poderosos quanto os autómatos em árvore não-determinísticos) (pt) |
| dbo:thumbnail | wiki-commons:Special:FilePath/DFA_example_multiplies_of_3.svg?width=300 |
| dbo:wikiPageExternalLink | http://lethal.sourceforge.net/ https://people.irisa.fr/Thomas.Genet/timbuk https://hal.inria.fr/hal-03367725/document%7C http://www.fit.vutbr.cz/research/groups/verifit/tools/libvata/ http://www.grappa.univ-lille3.fr/~filiot/tata/ http://afp.sourceforge.net/entries/Tree-Automata.shtml |
| dbo:wikiPageID | 98748 (xsd:integer) |
| dbo:wikiPageLength | 25218 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124441747 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Myhill–Nerode_theorem dbr:Deterministic_finite_automaton dbr:Deterministic_automaton dbr:Infinite-tree_automaton dbr:Arity dbr:String_(computer_science) dbr:Alternating_tree_automata dbr:Equivalence_relation dbr:Finite-state_automata dbr:Finite-state_transducer dbr:Tree_structure dbr:Ground_term dbr:Production_(computer_science) dbr:Regular_tree_grammar dbr:Courcelle's_theorem dbr:State_machine dbc:Theoretical_computer_science dbc:Automata_(computation) dbc:Formal_languages dbc:Trees_(data_structures) dbr:Ranked_alphabet dbr:Monadic_second-order_logic dbr:Regular_grammar dbr:S2S_(mathematics) dbr:Tree_transducers dbr:Regular_tree_language dbr:File:DFA_example_multiplies_of_3.svg |
| dbp:wikiPageUsesTemplate | dbt:Cite_arXiv dbt:Cite_book dbt:Cn dbt:Color dbt:For dbt:Reflist dbt:Sfn dbt:Harvid dbt:Formal_languages_and_grammars |
| dcterms:subject | dbc:Theoretical_computer_science dbc:Automata_(computation) dbc:Formal_languages dbc:Trees_(data_structures) |
| gold:hypernym | dbr:Machine |
| rdf:type | dbo:Software |
| rdfs:comment | En informatique théorique, plus précisément en théorie des langages, un automate d'arbre est une machine à états qui prend en entrée un arbre, plutôt qu'une chaîne de caractères pour les automates plus conventionnels, comme les automates finis. (fr) A tree automaton is a type of state machine. Tree automata deal with tree structures, rather than the strings of more conventional state machines. The following article deals with branching tree automata, which correspond to regular languages of trees. (en) Um autómato de árvore é um tipo de máquina de estados que lida com estruturas em árvore (de topologia em árvore), ao invés de strings como as máquinas de estado mais convencionais. Tal como acontece com os autómatos clássicos, um autómato de árvores finito (FTA) pode ser um autómato determinístico ou não. De acordo com a maneira que o autómato processa a árvore de entrada, o autómato de árvores finito pode ser de dois tipos: (a) bottom-up, (b) top-down. Essa é uma questão importante, pois apesar de os autómatos finitos de árvore não-determinísticos bottom-up e top-down serem equivalentes em poder expressivo, os autómatos determinísticos top-down são estritamente menos poderosos do que seus homólogos em bottom-up, por que as propriedades especificadas pelo autómato de árvores determinístico (pt) |
| rdfs:label | Automate d'arbres (fr) Autómato de árvore (pt) Tree automaton (en) |
| owl:sameAs | freebase:Tree automaton wikidata:Tree automaton dbpedia-fa:Tree automaton dbpedia-fr:Tree automaton dbpedia-pt:Tree automaton dbpedia-vi:Tree automaton https://global.dbpedia.org/id/2ffTm |
| prov:wasDerivedFrom | wikipedia-en:Tree_automaton?oldid=1124441747&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/DFA_example_multiplies_of_3.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Tree_automaton |
| is dbo:wikiPageRedirects of | dbr:Nondeterministic_finite_tree_automaton dbr:Nondeterministic_tree_automaton dbr:Top-down_tree_automaton dbr:Pumping_lemma_for_regular_tree_languages dbr:DFTA dbr:Tree_automata dbr:Tree_language dbr:Deterministic_finite_tree_automaton dbr:Deterministic_tree_automaton dbr:Bottom-up_tree_automaton |
| is dbo:wikiPageWikiLink of | dbr:List_of_computability_and_complexity_topics dbr:NFTA dbr:Nondeterministic_finite_tree_automaton dbr:Nondeterministic_tree_automaton dbr:Top-down_tree_automaton dbr:List_of_important_publications_in_theoretical_computer_science dbr:Infinite-tree_automaton dbr:Alternating_finite_automaton dbr:Regular_language dbr:Regular_tree_grammar dbr:Bottom-up dbr:Courcelle's_theorem dbr:Automata_theory dbr:Pumping_lemma_for_regular_tree_languages dbr:DFTA dbr:Monadic_second-order_logic dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Finite-state_machine dbr:Malware_research dbr:Pebble_automaton dbr:S2S_(mathematics) dbr:Tree-walking_automaton dbr:Tree_automata dbr:Tree_language dbr:Deterministic_finite_tree_automaton dbr:Deterministic_tree_automaton dbr:Bottom-up_tree_automaton |
| is foaf:primaryTopic of | wikipedia-en:Tree_automaton |
