| http://dbpedia.org/ontology/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.
, A tree automaton is a type of state machin … 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.)mata are as powerful as ND tree automata.)
, Um autómato de árvore é um tipo de máquina … 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)s autómatos em árvore não-determinísticos)
|
| http://dbpedia.org/ontology/thumbnail
|
http://commons.wikimedia.org/wiki/Special:FilePath/DFA_example_multiplies_of_3.svg?width=300 +
|
| http://dbpedia.org/ontology/wikiPageExternalLink
|
https://hal.inria.fr/hal-03367725/document%7C +
, https://people.irisa.fr/Thomas.Genet/timbuk +
, http://www.grappa.univ-lille3.fr/~filiot/tata/ +
, http://lethal.sourceforge.net/ +
, http://www.fit.vutbr.cz/research/groups/verifit/tools/libvata/ +
, http://afp.sourceforge.net/entries/Tree-Automata.shtml +
|
| http://dbpedia.org/ontology/wikiPageID
|
98748
|
| http://dbpedia.org/ontology/wikiPageLength
|
25218
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1124441747
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Deterministic_automaton +
, http://dbpedia.org/resource/Category:Formal_languages +
, http://dbpedia.org/resource/Finite-state_transducer +
, http://dbpedia.org/resource/Regular_tree_grammar +
, http://dbpedia.org/resource/Monadic_second-order_logic +
, http://dbpedia.org/resource/Regular_grammar +
, http://dbpedia.org/resource/String_%28computer_science%29 +
, http://dbpedia.org/resource/Courcelle%27s_theorem +
, http://dbpedia.org/resource/Tree_structure +
, http://dbpedia.org/resource/Production_%28computer_science%29 +
, http://dbpedia.org/resource/S2S_%28mathematics%29 +
, http://dbpedia.org/resource/Ranked_alphabet +
, http://dbpedia.org/resource/Infinite-tree_automaton +
, http://dbpedia.org/resource/Finite-state_automata +
, http://dbpedia.org/resource/Equivalence_relation +
, http://dbpedia.org/resource/Category:Automata_%28computation%29 +
, http://dbpedia.org/resource/Ground_term +
, http://dbpedia.org/resource/Arity +
, http://dbpedia.org/resource/Myhill%E2%80%93Nerode_theorem +
, http://dbpedia.org/resource/Category:Trees_%28data_structures%29 +
, http://dbpedia.org/resource/State_machine +
, http://dbpedia.org/resource/Regular_tree_language +
, http://dbpedia.org/resource/Deterministic_finite_automaton +
, http://dbpedia.org/resource/Category:Theoretical_computer_science +
, http://dbpedia.org/resource/Tree_transducers +
, http://dbpedia.org/resource/Alternating_tree_automata +
, http://dbpedia.org/resource/File:DFA_example_multiplies_of_3.svg +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Cite_book +
, http://dbpedia.org/resource/Template:Sfn +
, http://dbpedia.org/resource/Template:Cite_arXiv +
, http://dbpedia.org/resource/Template:Color +
, http://dbpedia.org/resource/Template:For +
, http://dbpedia.org/resource/Template:Cn +
, http://dbpedia.org/resource/Template:Reflist +
, http://dbpedia.org/resource/Template:Harvid +
, http://dbpedia.org/resource/Template:Formal_languages_and_grammars +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Theoretical_computer_science +
, http://dbpedia.org/resource/Category:Trees_%28data_structures%29 +
, http://dbpedia.org/resource/Category:Formal_languages +
, http://dbpedia.org/resource/Category:Automata_%28computation%29 +
|
| http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Machine +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Tree_automaton?oldid=1124441747&ns=0 +
|
| http://xmlns.com/foaf/0.1/depiction
|
http://commons.wikimedia.org/wiki/Special:FilePath/DFA_example_multiplies_of_3.svg +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Tree_automaton +
|
| owl:sameAs |
https://global.dbpedia.org/id/2ffTm +
, http://rdf.freebase.com/ns/m.0p8rz +
, http://www.wikidata.org/entity/Q2872598 +
, http://fa.dbpedia.org/resource/%D9%85%D8%A7%D8%B4%DB%8C%D9%86_%D8%AF%D8%B1%D8%AE%D8%AA%DB%8C +
, http://pt.dbpedia.org/resource/Aut%C3%B3mato_de_%C3%A1rvore +
, http://dbpedia.org/resource/Tree_automaton +
, http://fr.dbpedia.org/resource/Automate_d%27arbres +
, http://vi.dbpedia.org/resource/%C3%94t%C3%B4mat_c%C3%A2y +
|
| rdf:type |
http://dbpedia.org/ontology/Software +
|
| rdfs:comment |
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 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.
, Um autómato de árvore é um tipo de máquina … 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ísticoas pelo autómato de árvores determinístico
|
| rdfs:label |
Automate d'arbres
, Autómato de árvore
, Tree automaton
|
