A Graph-Based Classical and Quantum Approach to Deterministic L-System Inference
This work addresses the time-consuming manual process of finding L-systems for modeling biological processes like plant development, offering an automated solution from data, though it appears incremental as it builds on existing graph and algorithmic approaches.
The paper tackles the problem of automatically inferring deterministic context-free L-systems (D0L-systems) from string sequences, which is typically done manually by experts, by introducing a characteristic graph to translate it into maximum independent set and SAT problems, and provides a classical exact algorithm and an approximate quantum algorithm for this inference.
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.