Designing and Learning Substitutable Plane Graph Grammars
| Autor: | Tim Oates, Frédéric Papadopoulos, Rémi Eyraud, Jean-Christophe Janodet |
|---|---|
| Přispěvatelé: | Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), éQuipe AppRentissage et MultimediA [Marseille] (QARMA), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Informatique, Biologie Intégrative et Systèmes Complexes (IBISC), Université d'Évry-Val-d'Essonne (UEVE), CoRaL, Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
Computer science
media_common.quotation_subject graph grammars computer.software_genre Theoretical Computer Science symbols.namesake Rule-based machine translation grammatical inference [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG] distributional learning Time complexity media_common Planar embedding Discrete mathematics Algebra and Number Theory Parsing Grammar Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Rotation formalisms in three dimensions Grammar induction Planar graph Plane graphs Computational Theory and Mathematics symbols computer Information Systems MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Fundamenta Informaticae Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2016, Grammatical Inference, 146 (4), pp.403-430. ⟨10.3233/FI-2016-1393⟩ Fundamenta Informaticae, 2016, Grammatical Inference, 146 (4), pp.403-430. ⟨10.3233/FI-2016-1393⟩ |
| ISSN: | 0169-2968 |
| DOI: | 10.3233/FI-2016-1393⟩ |
| Popis: | International audience; Though graph grammars have been widely investigated for 40 years, few learning results exist for them. The main reasons come from complexity issues that are inherent when graphs, and a fortiori graph grammars, are considered. The picture is however different if one considers drawings of graphs, rather than the graphs themselves. E.g., it has recently been proved that the isomorphism and pattern searching problems could be solved in polynomial time for plane graphs, that is, planar embedding of planar graphs. In this paper, we introduce the Plane Graph Grammars (PGG) and detail how they differ to usual graph grammar formalisms while at the same time they share important properties with string context-free grammars. In particular, the parsing of a graph with a given PGG is polynomial for languages with appropriate restrictions. We demonstrate that PGG are well-shaped for learning: we show how recent results on string grammars can be extended to PGG by providing a learning algorithm that identifies in the limit the class of substitutable plane graph languages. Our algorithm runs in polynomial time assuming the same restriction used for polynomial parsing, and the amount of data needed for convergence is comparable to the one required in the case of strings. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|