Classical and Quantum Algorithms for the Deterministic L-system Inductive Inference Problem

Autor:	Lotfi, Ali, McQuillan, Ian, Rayan, Steven
Rok vydání:	2024
Předmět:	Quantum Physics Computer Science - Computation and Language Computer Science - Data Structures and Algorithms Computer Science - Formal Languages and Automata Theory Computer Science - Machine Learning
Druh dokumentu:	Working Paper
Popis:	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 hugely 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-system) 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. Comment: 16 pages, 1 figure
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2411.19906 Zobrazit plný text záznamu View this record from Arxiv