A characteristic-graph reduction for deterministic L-system inference with classical and quantum-heuristic solvers
Abstract L-systems can be made to model and create simulations of many biological processes, such as plant development. Finding an L-system for a given process is typically solved by hand, by experts, in a massively time-consuming process. It would be significant if this could be done automatically from data, such as from sequences of images. In this paper, we are interested in inferring a particular type of L-system, deterministic context-free L-system (D0L-system) from a sequence of strings. We introduce the characteristic graph of a sequence of strings, which we then utilize to translate our problem (inferring D0L-systems) in polynomial time into the maximum independent set problem (MIS) and the SAT problem. After that, we offer a classical exact algorithm and an approximate quantum algorithm for the problem.
Authors
- Steven Rayan (ORCID: https://orcid.org/0000-0003-0273-1598)
- Ian McQuillan (ORCID: https://orcid.org/0000-0002-7998-4430)
- Ali Lotfi (ORCID: https://orcid.org/0000-0003-1478-542X)
Institutions
- University of Saskatchewan (CA)
Publication Details
- Journal
- Research in the Mathematical Sciences
- Published
- 2026-11-14
- DOI
- https://doi.org/10.1007/s40687-026-00667-2
- Primary Topic
- semigroups and automata theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00