| 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
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 20483 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| 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
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
