Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Issue title: Grammatical Inference
Guest editors: Rémi Eyraud, Colin de la Higuera, Makoto Kanazawa and Ryo Yoshinaka
Article type: Research Article
Authors: Eyraud, Rémia; * | Janodet, Jean-Christopheb | Oates, Timc | Papadopoulos, Frédéricd
Affiliations: [a] Qarma Team, LIF Marseille, France. [email protected] | [b] IBISC lab, University of Evry, 23 Bd de France, F-91037 Evry, France. [email protected] | [c] CoRaL lab, CSEE department, University of Maryland, Baltimore County, USA | [d] IBISC lab, University of Evry, 23 Bd de France, F-91037 Evry, France
Correspondence: [*] Address for correspondence: 39 rue F. Joliot Curie 13453, Marseille cedex 13, France
Abstract: 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. For instance, it has recently been proved that the isomorphism and pattern searching problems could be solved in polynomial time for plane graphs, that is, planar embeddings of planar graphs. In this paper, we introduce the Plane Graph Grammars (PGG) and detail how they differ to usual graph grammar formalism’s while at the same time they share important properties with string context-free grammars. In particular, though exponential in the general case, we provide an appropriate restriction on languages that allows the parsing of a graph with a given PGG in polynomial time. 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.
Keywords: Plane graphs, graph grammars, distributional learning, grammatical inference
DOI: 10.3233/FI-2016-1393
Journal: Fundamenta Informaticae, vol. 146, no. 4, pp. 403-430, 2016
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
[email protected]
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office [email protected]
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
如果您在出版方面需要帮助或有任何建, 件至: [email protected]