Fundamenta Informaticae - Volume 146, issue 4

Authors: Eyraud, Rémi | de la Higuera, Colin | Kanazawa, Makoto | Yoshinaka, Ryo

Article Type: Other

DOI: 10.3233/FI-2016-1390

Citation: Fundamenta Informaticae, vol. 146, no. 4, pp. i-ii, 2016

Authors: Clark, Alexander | Kanazawa, Makoto | Kobele, Gregory M. | Yoshinaka, Ryo

Article Type: Research Article

Abstract: A key component of Clark and Yoshinaka’s distributional learning algorithms is the extraction of substructures and contexts contained in the input data. This problem often becomes intractable with nonlinear grammar formalisms due to the fact that more than polynomially many substructures and/or contexts may be contained in each object. Previous works on distributional learning of nonlinear grammars avoided this difficulty by restricting the substructures or contexts that are made available to the learner. In this paper, we identify two classes of nonlinear tree grammars for which the extraction of substructures and contexts can be performed in polynomial time, and which, …consequently, admit successful distributional learning in its unmodified, original form. Show more

Keywords: Distributional learning, tree language, tree pattern, generalized context-free grammar, parallel regular tree grammar, IO context-free tree grammar

DOI: 10.3233/FI-2016-1391

Citation: Fundamenta Informaticae, vol. 146, no. 4, pp. 339-377, 2016

Authors: Scicluna, James | de la Higuera, Colin

Article Type: Research Article

Abstract: Recently, different theoretical learning results have been found for a variety of context-free grammar subclasses through the use of distributional learning [1]. However, these results are still not extended to probabilistic grammars. In this work, we give a practical algorithm, with some proven properties, that learns a subclass of probabilistic grammars from positive data. A minimum satisfiability solver is used to direct the search towards small grammars. Experiments on well-known context-free languages and artificial natural language grammars give positive results. Moreover, our analysis shows that the type of grammars induced by our algorithm are, in theory, capable of modelling context-free …features of natural language syntax. One of our experiments shows that our algorithm can potentially outperform the state-of-the-art in unsupervised parsing on the WSJ10 corpus. Show more

Keywords: Grammatical Inference, Probabilistic Context-Free Grammars, Minimum Satisfiability, Congruential Grammars, Small Grammars

DOI: 10.3233/FI-2016-1392

Citation: Fundamenta Informaticae, vol. 146, no. 4, pp. 379-402, 2016

Authors: Eyraud, Rémi | Janodet, Jean-Christophe | Oates, Tim | Papadopoulos, Frédéric

Article Type: Research Article

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. Show more

Keywords: Plane graphs, graph grammars, distributional learning, grammatical inference

DOI: 10.3233/FI-2016-1393

Citation: Fundamenta Informaticae, vol. 146, no. 4, pp. 403-430, 2016

Authors: Beros, Achilles A. | Higuera, Colin de la

Article Type: Research Article

Abstract: We prove the existence of a canonical form for semi-deterministic transducers with sets of pairwise incomparable output strings. Based on this, we develop an algorithm which learns semi-deterministic transducers given access to translation queries. We also prove that there is no learning algorithm for semi-deterministic transducers that uses only domain knowledge.

Keywords: Grammatical Inference, Semi-Deterministic Transducers

DOI: 10.3233/FI-2016-1394

Citation: Fundamenta Informaticae, vol. 146, no. 4, pp. 431-459, 2016

Article Type: Other

Citation: Fundamenta Informaticae, vol. 146, no. 4, pp. 461-462, 2016