The Garsia-Wachs algorithm is an algorithm for finding a leaf-labeled binary tree whose leaf sequence exactly matches the input weight sequence and whose cost is as small as possible, where the cost is the sum of the weights labeling the leaves multiplied by their levels. The algorithm, along with a proof of correctness due to Kingston, is presented in Knuth’s The Art of Computer Programming, Vol. 3. The algorithm comes in two versions, the naive and the optimized. Both versions have quadratic time complexity, but the optimized version can be fine-tuned with a suitable data structure to yield an O(n log n)-time algorithm. I implement and verify a variant of each version of the algorithm in the verification-aware programming language Dafny. Unlike all previous presentations of the algorithm, these variants construct the desired optimum tree directly, without detour through a "nonalphabetic" tree whose leaf sequence is a rearrangement of the input sequence.

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 con texts 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.

International audience

Weir [ 43 ] proved a Chomsky–Schützenberger-like representation theorem for the string languages of tree-adjoining grammars, where the Dyck language D n in the Chomsky–Schützenberger characterization is replaced by the intersection D 2 n ∩ g −1( D 2 n ), where g is a certain bijection on the alphabet consisting of 2 n pairs of brackets. This article presents a generalization of this theorem to the string languages generated by simple (i.e. linear and non-deleting) context-free tree grammars. This result is obtained through a natural generalization of the original Chomsky–Schützenberger theorem to the tree languages of simple context-free tree grammars. I use Baldwin and Strawn's [ 2 ] notion of multidimensional trees to state this latter theorem in a very general, abstract form.

versions of selected contributions presented at the 16th Workshop on Logic, Language, Information and Computation (WoLLIC 2009), held from June 21 through 24, 2009, in the National Center of Sciences, Tokyo, Japan.WoLLIC is a series of workshops which started in 1994 with the aim of fostering interdisciplinary research in pure and applied logic.The idea of the workshop is to have a forum which is large enough in the number of possible interactions between logic and the sciences related to information and computation, and yet is small enough to allow for concrete and useful interaction across logic-related disciplines.Held over the course of four full days, WoLLIC 2009 included both extended tutorial sessions and general lectures, given by an international panel of the world's top experts in the fields of theoretical and applied logic, linguistics, and computer science.The composition of the speakers and the other participants of the workshop reflected the diversity of the event: included were members of psycholinguistics, cognitive science, mathematics, philosophy, theoretical computer science and business software communities from geographical locales as close to home as Tokyo, to as far away places such as Brazil and Iran.The close contact between the speakers and the other participants ensued, within the intensive workshop environment, an intimate setting in which the free and fruitful exchange of ideas could take place.

Article Angluin's theorem for indexed families of r.e. sets and applications Share on Authors: Dick de Jongh Institute for Logic, Language and Computation, University of Amsterdam Institute for Logic, Language and Computation, University of AmsterdamView Profile , Makoto Kanazawa Department of Cognitive and Information Sciences, Chiba University Department of Cognitive and Information Sciences, Chiba UniversityView Profile Authors Info & Claims COLT '96: Proceedings of the ninth annual conference on Computational learning theoryJanuary 1996 Pages 193–204https://doi.org/10.1145/238061.238095Published:01 January 1996 26citation267DownloadsMetricsTotal Citations26Total Downloads267Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access