Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2411.19906 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912458658021376 |
|---|---|
| author | Lotfi, Ali McQuillan, Ian Rayan, Steven |
| author_facet | Lotfi, Ali McQuillan, Ian Rayan, Steven |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_19906 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Graph-Based Classical and Quantum Approach to Deterministic L-System Inference Lotfi, Ali McQuillan, Ian Rayan, Steven Quantum Physics Computation and Language Data Structures and Algorithms Formal Languages and Automata Theory Machine Learning 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. |
| title | A Graph-Based Classical and Quantum Approach to Deterministic L-System Inference |
| topic | Quantum Physics Computation and Language Data Structures and Algorithms Formal Languages and Automata Theory Machine Learning |
| url | https://arxiv.org/abs/2411.19906 |