Dakotah Lambert
dakotahlambert@acm.org
Visiting Assistant Professor of Computer Science at Haverford College
Interests
My work lies at the intersection of theoretical computer science, abstract algebra, and linguistics. Using connections between formal logic, finite automata, and algebra, I study the structures that arise in communication between and among humans and computers, including natural languages (human–human communication), programming languages (human–computer communication), and signaling protocols (computer–computer communication). Parameterization and decomposition of these systems arise out of their structure and inform mechanisms for recognition and learning. I have also applied these techniques to pattern-learning by neural networks, which provides insight and explainability for such models.
Projects
Over the years, I have been building an interactive theorem-prover for subregular logics. The custom domain-specific language, PLEB, and its interpreter, plebby, have been instrumental to my work. Implemented in Haskell as both a library and supporting command-line tools, the Language Toolkit (LTK) allows one to build finite automata from certain kinds of quantifier-free logical expressions, to extract logical descriptions of automata, and to classify the associated language with respect to a rich subregular hierarchy. This includes classes defined by logical properties as well as those induced by user-specified pseudovarieties of semigroups or monoids. This system is also available on Hackage.
Find more on Github.
Publications
- Sam van der Poel, Dakotah Lambert, Kalina Kostyszyn, Tiantian Gao, Rahul Verma, Derek Andersen, Joanne Chau, Emily Peterson, Cody St. Clair, Paul Fodor, Chihiro Shibata, and Jeffrey Heinz. 2024. MLRegTest: A benchmark for the machine learning of regular languages. Journal of Machine Learning Research, 25(283):1–45.
- Dakotah Lambert and Jeffrey Heinz. 2024. Algebraic reanalysis of phonological processes described as output-oriented. In Proceedings of the Society for Computation in Linguistics, volume 7, pages 129–138, Irvine, California.
- Dakotah Lambert. 2024. System description: A theorem-prover for subregular systems: The Language Toolkit and its interpreter, plebby. In Functional and Logic Programming: 17th Annual Symposium, FLOPS 2024, volume 14659 of Lecture Notes in Computer Science, pages 311–328, Kumamoto, Japan. Springer, Singapore.
- Philip Kaelbling, Dakotah Lambert, and Jeffrey Heinz. 2023. Robust identification in the limit from incomplete positive data. In Henning Fernau and Klaus Jansen, editors, Fundamentals of Computation Theory: 24th International Symposium, FCT 2023, volume 14292 of Lecture Notes in Computer Science, pages 276–290. Springer, Cham.
- Rémi Eyraud, Dakotah Lambert, Badr Tahri Joutei, Aidar Gaffarov, Mathias Cabanne, Jeffrey Heinz, and Chihiro Shibata. 2023. TAYSIR competition: Transformer+RNN: Algorithms to yield simple and interpretable representations. In Proceedings of the 16th edition of the International Conference on Grammatical Inference, volume 217 of Proceedings of Machine Learning Research, pages 275–290.
- Dakotah Lambert and Jeffrey Heinz. 2023. An algebraic characterization of total input strictly local functions. In Proceedings of the Society for Computation in Linguistics, volume 6, pages 25–34, Amherst, Massachusetts.
- Dakotah Lambert. 2023. Relativized adjacency. Journal of Logic, Language and Information, 32(4):707–731.
- Dakotah Lambert. 2022. Unifying Classification Schemes for Languages and Processes with Attention to Locality and Relativizations Thereof. Ph.D. thesis, Stony Brook University.
- Dakotah Lambert. 2021. Grammar interpretations and learning TSL online. In Proceedings of the Fifteenth International Conference on Grammatical Inference, volume 153 of Proceedings of Machine Learning Research, pages 81–91.
- Dakotah Lambert, Jonathan Rawski, and Jeffrey Heinz. 2021. Typology emerges from simplicity in representations and learning. Journal of Language Modelling, 9(1):151–194. Institute of Computer Science, Polish Academy of Sciences.
- Dakotah Lambert and James Rogers. 2020. Tier-based strictly local stringsets: Perspectives from model and automata theory. In Proceedings of the Society for Computation in Linguistics, volume 3, pages 330–337, New Orleans, Louisiana.
- James Rogers and Dakotah Lambert. 2019. Extracting Subregular constraints from Regular stringsets. Journal of Language Modelling, 7(2):143–176. Institute of Computer Science, Polish Academy of Sciences.
- James Rogers and Dakotah Lambert. 2019. Some classes of sets of structures definable without quantifiers. In Proceedings of the 16th Meeting on the Mathematics of Language, pages 63–77, Toronto, Canada. Association for Computational Linguistics.
- Dakotah Lambert and James Rogers. 2019. A logical and computational methodology for exploring systems of phonotactic constraints. In Proceedings of the Society for Computation in Linguistics, volume 2, pages 247–256, New York City, New York.
- James Rogers and Dakotah Lambert. 2017. Extracting forbidden factors from Regular stringsets. In Proceedings of the 15th Meeting on the Mathematics of Language, pages 36–46, London, UK. Association for Computational Linguistics.
- Dakotah Lambert, Margaret Fero, Andrew Dai, and James Rogers. 2014. A workbench for logically definable stringsets. In Proceedings of the 2014 Midstates Conference for Undegraduate Research in Computer Science and Mathematics, pages 47–52, Wooster, OH.
- James Rogers, Jeffrey Heinz, Margaret Fero, Jeremy Hurst, Dakotah Lambert, and Sean Wibel. 2012. Cognitive and sub-regular complexity. In Glyn Morrill and Mark-Jan Nederhof, editors, Formal Grammar 2012, volume 8036 of Lecture Notes in Computer Science, pages 90–108. Springer Verlag.
Talks
- Dakotah Lambert. 2024. Abstract algebra and the subregular hierarchy. The 2024 Rutgers Subregular Phonology Workshop, September 27–29, New Brunswick, New Jersey.
- Dakotah Lambert. 2024. Algebraic analyses of phonology. Workshop on Algebraic Models of Generative Linguistics. March 8--10, Merkin Center for Pure and Applied Mathematics.
- Dakotah Lambert. 2024. Constraint-driven analysis of formal languages. Automata seminar, Institut de Recherche en Informatique Fondamentale (IRIF), February 16.