Nested word (original) (raw)
In computer science, more specifically in automata and formal language theory, nested words are a concept proposed by Alur and Madhusudan as a joint generalization of words, as traditionally used for modelling linearly ordered structures, and of ordered unranked trees, as traditionally used for modelling hierarchical structures. Finite-state acceptors for nested words,so-called nested word automata, then give a more expressive generalization of finite automata on words. The linear encodings of languages accepted by finite nested word automata gives the class of visibly pushdown languages. The latter language class lies properly between the regular languages and the deterministic context-free languages. Since their introduction in 2004, these concepts have triggered much research in that ar
| Property | Value |
|---|---|
| dbo:abstract | En informatique théorique, et notamment en théorie des automates et des langages formels, un automate à pile visible (en anglais « visibly pushdown automaton ») est un automate à pile reconnaissant des mots sur un alphabet partitionné. Ils reconnaissent les langages à pile visible (en anglais « visibly pushdown languages »). Cette famille de langages est intermédiaire entre les langages rationnels et les langages algébriques déterministes. Un mot imbriqué (en anglais « nested word »), notion proposée par Rajeev Alur et Parthasarathy Madhusudan, est un objet doté d'une double structure : d'un côté, c'est une chaîne de caractères, comme dans l’usage traditionnel de la modélisation de structures totalement ordonnées, d'un autre côté, c'est un modèle de structure hiérarchique, comme les arbres enracinés ou les systèmes de parenthèses emboîtées. Les automates acceptant des ensembles de mots imbriqués sont les automates de mots imbriqués (en anglais « nested word automata »). Ce sont des automates généralisant les automates finis de mots. Le codage par système de parenthèses de mots imbriqués redonne la classe des langages à pile visible. Depuis l'introduction de cette terminologie par Alur et Madhusudan en 2004, suivie d'un développement autour de ces notions en 2009, ces concepts ont déclenché un nombre important de recherches sur et autour de ces objets et de leur applications. (fr) In computer science, more specifically in automata and formal language theory, nested words are a concept proposed by Alur and Madhusudan as a joint generalization of words, as traditionally used for modelling linearly ordered structures, and of ordered unranked trees, as traditionally used for modelling hierarchical structures. Finite-state acceptors for nested words,so-called nested word automata, then give a more expressive generalization of finite automata on words. The linear encodings of languages accepted by finite nested word automata gives the class of visibly pushdown languages. The latter language class lies properly between the regular languages and the deterministic context-free languages. Since their introduction in 2004, these concepts have triggered much research in that area. (en) Em ciência da computação, mais especificamente em teoria do autômato e teoria de linguagem formal, palavras aninhadas são um conceito proposto por Alur e Madhusudan como uma generalização conjunta de palavras, tradicionalmente usada para modelagem de estruturas linearmente ordenadas e de árvores ordenadas sem classificação, como também utilizadas para modelagem de estruturas hierárquicas. Os aceitadores de estado finito para palavras aninhadas são chamados de autômatos de palavras aninhadas, assim generalizando, de maneira mais expressiva, autômatos finitos não determinísticos sobre palavras. As codificações lineares de linguagens aceitas por autômatos finitos de palavra aninhada resultam em uma classe de linguagem visivelmente de pilha. A última classe de linguagem fica entre linguagens regulares e as linguagens livres de contexto determinísticas. Desde sua introdução, em 2004, esses conceitos têm desencadeado muitas pesquisas na área. (pt) |
| dbo:wikiPageExternalLink | https://web.archive.org/web/20100712200228/http:/www.cs.uiuc.edu/~madhu/vpa/ https://web.archive.org/web/20120809152133/http:/qwiki.stanford.edu/index.php/Complexity_Zoo:V%23vpl http://www.cis.upenn.edu/~alur/nw.html http://users.utu.fi/aleokh/papers/linconj_vs_dcfl.pdf |
| dbo:wikiPageID | 24286709 (xsd:integer) |
| dbo:wikiPageLength | 20483 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1062679466 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Pushdown_automaton dbr:Monadic_predicate_calculus dbr:Nondeterministic_finite_automaton dbr:Nonnegative_integer dbr:Deterministic_finite_automaton dbr:Deterministic_context-free_language dbr:Deterministic_pushdown_automaton dbr:Rajeev_Alur dbr:Complexity_Zoo dbr:Concatenation dbr:Context-free_grammar dbr:Operator-precedence_grammar dbr:Model_checking dbr:Alphabet_(computer_science) dbr:Computer_science dbr:Deterministic_pushdown_automata dbr:String_(computer_science) dbr:String_operations dbr:Tree_(data_structure) dbr:Tuple dbr:EXPTIME dbr:Formal_language dbr:Regular_language dbc:Automata_(computation) dbc:Formal_languages dbr:Chomsky_hierarchy dbr:Automata_theory dbc:Words dbr:Boolean_algebra_(structure) dbr:Boolean_circuit dbr:Conjunctive_grammars dbr:Kleene_star dbr:SO_(complexity) dbr:Linearly_ordered dbr:String_homomorphism |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_journal dbt:Harv dbt:Harvtxt dbt:Math dbt:Formal_languages_and_grammars |
| dct:subject | dbc:Automata_(computation) dbc:Formal_languages dbc:Words |
| gold:hypernym | dbr:Concept |
| rdf:type | yago:Abstraction100002137 yago:Communication100033020 yago:Language106282651 yago:WikicatFormalLanguages |
| rdfs:comment | In computer science, more specifically in automata and formal language theory, nested words are a concept proposed by Alur and Madhusudan as a joint generalization of words, as traditionally used for modelling linearly ordered structures, and of ordered unranked trees, as traditionally used for modelling hierarchical structures. Finite-state acceptors for nested words,so-called nested word automata, then give a more expressive generalization of finite automata on words. The linear encodings of languages accepted by finite nested word automata gives the class of visibly pushdown languages. The latter language class lies properly between the regular languages and the deterministic context-free languages. Since their introduction in 2004, these concepts have triggered much research in that ar (en) En informatique théorique, et notamment en théorie des automates et des langages formels, un automate à pile visible (en anglais « visibly pushdown automaton ») est un automate à pile reconnaissant des mots sur un alphabet partitionné. Ils reconnaissent les langages à pile visible (en anglais « visibly pushdown languages »). Cette famille de langages est intermédiaire entre les langages rationnels et les langages algébriques déterministes. (fr) Em ciência da computação, mais especificamente em teoria do autômato e teoria de linguagem formal, palavras aninhadas são um conceito proposto por Alur e Madhusudan como uma generalização conjunta de palavras, tradicionalmente usada para modelagem de estruturas linearmente ordenadas e de árvores ordenadas sem classificação, como também utilizadas para modelagem de estruturas hierárquicas. Os aceitadores de estado finito para palavras aninhadas são chamados de autômatos de palavras aninhadas, assim generalizando, de maneira mais expressiva, autômatos finitos não determinísticos sobre palavras. As codificações lineares de linguagens aceitas por autômatos finitos de palavra aninhada resultam em uma classe de linguagem visivelmente de pilha. A última classe de linguagem fica entre linguagens r (pt) |
| rdfs:label | Automate à pile visible (fr) Nested word (en) Palavra aninhada (pt) |
| owl:sameAs | freebase:Nested word yago-res:Nested word wikidata:Nested word dbpedia-fa:Nested word dbpedia-fr:Nested word dbpedia-pt:Nested word https://global.dbpedia.org/id/4sTQB |
| prov:wasDerivedFrom | wikipedia-en:Nested_word?oldid=1062679466&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Nested_word |
| is dbo:wikiPageRedirects of | dbr:Visibly_pushdown_automaton dbr:Nested_word_automata dbr:Visibly_pushdown_language dbr:Nested_words |
| is dbo:wikiPageWikiLink of | dbr:Rajeev_Alur dbr:Regular_tree_grammar dbr:VPL dbr:Visibly_pushdown_automaton dbr:Nested_word_automata dbr:Visibly_pushdown_language dbr:Nested_words |
| is foaf:primaryTopic of | wikipedia-en:Nested_word |