Invited speakers
In addition to contributed and informal talks, NCMA 2025 will feature two invited speakers, including one joint invitation with DCFS 2025. Learn more about their backgrounds and the topics of their talks in the bios and abstracts below.
Laure Daviaud
University of East Anglia, UK
Laure Daviaud is Associate Professor in Computing Sciences at the University of East Anglia (UEA).
Her research interests lie in automata theory and logic, with a particular focus on weighted automata and problems around the decidability of comparison and minimisation and the theory of learning.
She obtained her PhD in 2014 from the University Paris VII, under the supervision of Thomas Colcombet and Jean-Eric Pin and after post-doctoral positions at Aix-Marseille University, ENS Lyon, the University of Warsaw and the University of Warwick, she became lecturer at City, University of London before moving to UEA.
Abstract Weighted automata and cost register automata: (Un)Decidability
Laure Daviaud
Weighted automata, and their equivalent cost register automata are a quantitative model of automata, mapping words to values such as costs or probabilities.
In this talk, I will give a broad overview of decidability problems for them: what is known and what is still open, regarding problems such as equivalence, approximation and determinisation.
Ian McQuillan
University of Saskatchewan, Canada
Ian McQuillan is a Professor of Computer Science at the University of Saskatchewan in Canada.
His research focuses on formal language and automata theory, computational complexity, computational biology, and natural computing.
He finished his Ph.D. under the supervision of Professor Helmut Jürgensen in 2005 at Western University in Canada. Within automata theory, he has specialized in unconventional models of computation and grammar models with restricted power, while studying decision problems on them. His research is supported by the Natural Sciences and Engineering Research Council of Canada.
Abstract Inductive Inference of Lindenmayer Systems: Computational and Descriptional Complexity
Ian McQuillan
Grammatical inference involves the learning of formal grammars from data, and inductive inference involves the learning of grammars from positive examples of words that are generated.
In this talk, we will present inductive inference of different types of Lindenmayer systems (L-systems). L-systems are particularly useful for creating simulations of plants and other processes with inherent parallelism. We mostly analyze the problem of being given one or more sequences of strings initially generated by an (unknown) L-system and attempting to infer an L-system that indeed can initially generate those sequences.
This includes different restrictions on L-systems such as deterministic, nondeterministic, tabled, non-tabled, erasing, non-erasing, context-free, context-sensitive, or parametric. We will survey older results on decidability of inference, and newer results on complexity.
Computational complexity will go hand-in-hand with descriptional complexity as we will strive to inductively infer L-systems with the smallest number of rewriting rules and/or the smallest number of tables. Computational complexity will also vary depending upon whether certain parameters of the L-system are taken to be fixed or not, leading to fixed-parameter tractable algorithms.
We also discuss more experimental results with implementations of inductive inference. Finally, we describe preliminary work on learning and matching L-systems to images.
There are many interesting open problems and future directions that remain in this area, which will be discussed.