About LAL

Publications describing LAL.

Authored by the creators of LAL

Publications authored by the creators of LAL, but not about LAL.

Whose algorithms/formulas are implemented in LAL

Publications that present algorithms/formulas implemented in LAL.

  • Alemany-Puig, L. and Esteban, J. L. and Ferrer-i-Cancho, R. (2022) Maximum Linear Arrangement Problem for Trees under projectivity and planarity, under review. arXiv url:
  • Alemany-Puig, L. and Ferrer-i-Cancho, R. (2022) Linear time calculation of the expected sum of edge lengths in projective linearizations of trees. Journal of Computational Linguistics, in press. DOI:
  • Lluís Alemany-Puig, Juan Luis Esteban, and Ramon Ferrer-i-Cancho. Minimum projective linearizations of trees in linear time. Information Processing Letters, 174:106204, 2022.
  • Lluís Alemany-Puig and Ramon Ferrer-i-Cancho. Fast calculation of the variance of edge crossings. Arxiv, 2021.
  • Lluís Alemany-Puig and Ramon Ferrer-i-Cancho. Edge crossings in random linear arrangements. Journal of Statistichal Mechanics, 2020:023403, 2020.
  • Lluís Alemany-Puig. Edge crossings in linear arrangements: from theory to algorithms and applications. Master Thesis (M. Sc.), 2019. Handle:
  • Daniel Gildea and David Temperley. Optimizing grammars for minimum dependency length. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 184–191, Prague, Czech Republic, June.
  • The gnu multiple precision arithmetic library. Accessed: 2020-03-24.
  • Luka Marohnić. Graph theory package for giac/xcas – reference manual. Accessed: 2020-01-13.
  • Ramon Ferrer-i-Cancho. The sum of edge lengths in random linear arrangements. Journal of Statistical Mechanics: Theory and Experiment, 2019:053401, 05 2019.
  • Patrick Bennett, Sean English, and Maria Talanda-Fisher. Weighted Turán problems with applications. Discrete Mathematics, 342(8):2165–2172, 2019.
  • Ramon Ferrer-i-Cancho, Carlos Gómez-Rodríguez, and Juan Luis Esteban. Are crossing dependencies really scarce? Physica A: Statistical Mechanics and its Applications, 493:311–329, 2018.
  • Esteban, J. L. & R. Ferrer-i-Cancho, R. (2017). A correction on Shiloach’s algorithm for minimum linear arrangement of trees. SIAM Journal of Computing 46(3), 1146-1151. doi: 10.1137/15M1046289.
  • Sylvain Kahane, Chunxiao Yan, and Marie-Amélie Botalla. What are the limitations on the flux of syntactic dependencies? evidence from ud treebanks. pages 73–82, 9 2017.
  • Richard Futrell, Kyle Mahowald, and Edward Gibson. Large-scale evidence of dependency length minimization in 37 languages. Proceedings of the National Academy of Sciences, 112(33):10336–10341 (2015).
  • Yingqi Jing and Haitao Liu. Mean Hierarchical Distance: Augmenting Mean Dependency Distance. Proceedings of the Third International Conference on Dependency Linguistics (Depling 2015), (Depling):161–170, (2015).
  • Ramon Ferrer-i-Cancho. A stronger null hypothesis for crossing dependencies. CoRR, abs/1410.5485, 2014.
  • Giorgio Satta, Emily Pitler, Sampath Kannan, and Mitchell Marcus. Finding Optimal 1-Endpoint-Crossing Trees. pages 13–24, 2013.
  • Carlos Gómez-Rodríguez, John Carroll, and David Weir. Dependency Parsing Schemata and Mildly Non-Projective Dependency Parsing. Computational Linguistics, 37:541–586, 2011.
  • Haitao Liu. Dependency direction as a means of word-order typology: a method based on dependency treebanks. Lingua, 120(6):1567–1578, 2010.
  • Robert A. Hochberg and Matthias F. Stallmann. Optimal one-page tree embeddings in linear time. Information Processing Letters, 87(2):59–66, 2003.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, Cambridge, MA, USA, 2nd edition, 2001.
  • Mikhail Anatolievich Iordanskii. Minimal numberings of the vertices of trees — approximate approach. In Lothar Budach, Rais Gatic Bukharajev, and Oleg Borisovic Lupanov, editors, Fundamentals of Computation Theory, pages 214–217, Berlin, Heidelberg, 1987. Springer Berlin Heidelberg.
  • Fan R. K. Chung. On optimal linear arrangements of trees. Computers and Mathematics with Applications, 10(1):43–60, 1984.
  • Herbert S. Wilf. The uniform selection of free trees. Journal of Algorithms, 2:204–207, 1981.
  • Terry Beyer and Sandra Mitchell Hedetniemi. Constant time generation of rooted trees. SIAM Journal on Computing, 9(4):706–712, 1980.
  • Yossi Shiloach. A minimum linear arrangement algorithm for undirected trees. Society for Industrial and Applied Mathematics, 8(1):15–32, 1979.
  • Albert Nijenhuis and Herbert S. Wilf. Combinatorial Algorithms: For Computers and Hard Calculators. Academic Press, Inc., Orlando, FL, USA, 2nd edition, 1978.
  • A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley series in computer science and information processing. Addison-Wesley Publishing Company, Michigan University, 1st edition, 1974.
  • Frank Harary and Allen J. Schwenk. The number of caterpillars. Discrete Mathematics, 6:359–365, 1973.
  • Frank Harary. Graph Theory. CRC Press, Boca Raton, FL, USA, 2nd edition, 1969.
  • Richard Otter. Annals of Mathematics The Number of Trees. 49(3):583–599, 1948.
  • H. Prüfer. Neuer Beweis eines Satzes über Permutationen. Arch. Math. Phys, 27:742–744, 1918.
  • N. J. A. Sloane. The on-line encyclopedia of integer sequences – a000055 – number of trees with n unlabeled nodes. Accessed: 2019-12-28.
  • N. J. A. Sloane. The on-line encyclopedia of integer sequences – a000081 – number of unlabeled rooted trees with n nodes (or connected functions with a fixed point). Accessed: 2019-03-31.
  • Robert Alan Wright, Bruce Richmond, Andrew Odlyzko, and Brendan D. McKay. Constant time generation of free trees. SIAM Journal on Computing, 15:540–548, 05 1986.

That use LAL, or describe code integrated in LAL

That is, publications that use LAL directly or that have used code from it.

  • Ferrer-i-Cancho, R. & Gómez-Rodríguez, C. (2021). Dependency distance minimization predicts compression. Proceedings of the Second Workshop on Quantitative Syntax (Quasy, SyntaxFest 2021), 45-57.
  • Esteban, J. L. & R. Ferrer-i-Cancho, R. (2017). A correction on Shiloach’s algorithm for minimum linear arrangement of trees. SIAM Journal of Computing 46(3), 1146-1151. doi: 10.1137/15M1046289
  • Esteban, J. L., Ferrer-i-Cancho, R., & Gómez-Rodríguez, C. (2016). The scaling of the minimum sum of edge lengths in uniformly random trees. Journal of Statistical Mechanics, 063401.