A Graph-Based Classical and Quantum Approach to Deterministic L-System Inference

A Graph-Based Classical and Quantum Approach to Deterministic L-System Inference | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article A Graph-Based Classical and Quantum Approach to Deterministic L-System Inference Ali Lotfi, Ian McQuillan, Steven Rayan This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-6890100/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version 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. Lindenmayer systems deterministic L-system inference maximum independent set quantum algorithms QAOA SAT encoding formal grammars symbolic learning Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-6890100","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":518477890,"identity":"0f8c98ed-fc9f-4e67-be74-164ecaeb6ff6","order_by":0,"name":"Ali Lotfi","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAvklEQVRIiWNgGAWjYDACduaGwz94bEBMZiK1MDM2PmaQSSNNS7Mxg81hErTwNzO2SRfknE+c3378sQFDjR1hLRKHgVpmnLmduOFMjnECw7FkIqwBapHg7QFqYchhPsDYQITj5MFa/p1LnN///DFQSz1hLQaHgd7n4TmQ2HAjwTiBseEwYS2GhxkbH87gSTbecOONsUHCseOEtcgdbz5w4AOPnez8/vTHEh9qqglrQQUJpGoYBaNgFIyCUYAdAAD9izrfZNoh8gAAAABJRU5ErkJggg==","orcid":"","institution":"University of Saskatchewan","correspondingAuthor":true,"prefix":"","firstName":"Ali","middleName":"","lastName":"Lotfi","suffix":""},{"id":518477893,"identity":"a742eb49-876a-4230-a944-c324de1c0259","order_by":1,"name":"Ian McQuillan","email":"","orcid":"","institution":"University of Saskatchewan","correspondingAuthor":false,"prefix":"","firstName":"Ian","middleName":"","lastName":"McQuillan","suffix":""},{"id":518477894,"identity":"21fdfd01-8070-4c98-8557-45136e554b67","order_by":2,"name":"Steven Rayan","email":"","orcid":"","institution":"University of Saskatchewan","correspondingAuthor":false,"prefix":"","firstName":"Steven","middleName":"","lastName":"Rayan","suffix":""}],"badges":[],"createdAt":"2025-06-13 17:38:14","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-6890100/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-6890100/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":92137333,"identity":"8a009842-881a-4e6c-ad41-9892d529b732","added_by":"auto","created_at":"2025-09-25 04:56:41","extension":"json","order_by":0,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":4143,"visible":true,"origin":"","legend":"","description":"","filename":"5b6c146e402e4dd8aab02c907b57f787.json","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/b0d6c0cb702fed889066380d.json"},{"id":92137334,"identity":"abcb419c-4a1a-42a0-9143-939967c4a4b6","added_by":"auto","created_at":"2025-09-25 04:56:41","extension":"xml","order_by":1,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":99797,"visible":true,"origin":"","legend":"","description":"","filename":"5b6c146e402e4dd8aab02c907b57f7871enriched.xml","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/a53e14df3dc30f20bbc0e05f.xml"},{"id":92137335,"identity":"5805eaee-cc6c-4d28-8f9f-f3afc18189b6","added_by":"auto","created_at":"2025-09-25 04:56:41","extension":"pdf","order_by":2,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":397792,"visible":true,"origin":"","legend":"","description":"","filename":"SpringerNatureLaTeXTemplate.pdf","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/cfef8d9420790436d1365032.pdf"},{"id":92137776,"identity":"ac883814-19ff-4fa0-98d4-631321903ef6","added_by":"auto","created_at":"2025-09-25 05:04:41","extension":"pdf","order_by":3,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":101648,"visible":true,"origin":"","legend":"","description":"","filename":"coverletter.pdf","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/55e50ca477a49a167a997f61.pdf"},{"id":92137337,"identity":"f7da0e84-53ee-41a3-ac85-598749697258","added_by":"auto","created_at":"2025-09-25 04:56:41","extension":"eps","order_by":4,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":2890,"visible":true,"origin":"","legend":"","description":"","filename":"empty.eps","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/69f60f8328d0c0b73d804653.eps"},{"id":92137779,"identity":"d8092593-9c70-4a86-86ab-59311591d9a4","added_by":"auto","created_at":"2025-09-25 05:04:41","extension":"eps","order_by":5,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":91593,"visible":true,"origin":"","legend":"","description":"","filename":"fig.eps","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/eb62f59f35942b031f93d3cd.eps"},{"id":92139123,"identity":"ba2cab37-7d8a-468d-bf5d-f676bf3fd416","added_by":"auto","created_at":"2025-09-25 05:12:41","extension":"bst","order_by":6,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":146013,"visible":true,"origin":"","legend":"","description":"","filename":"snapacite.bst","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/2b82ded4af089defc0257395.bst"},{"id":92137774,"identity":"ddad8891-baaf-4a69-bb32-41d45f677c14","added_by":"auto","created_at":"2025-09-25 05:04:41","extension":"bst","order_by":7,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":29828,"visible":true,"origin":"","legend":"","description":"","filename":"snaps.bst","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/a10ecffaf4964c704b1e4945.bst"},{"id":92137340,"identity":"868b9261-c4e2-48d4-a5a9-ae1094730610","added_by":"auto","created_at":"2025-09-25 04:56:41","extension":"aux","order_by":8,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":7816,"visible":true,"origin":"","legend":"","description":"","filename":"snarticle.aux","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/bbb7ac5a02abfe6ff82279dc.aux"},{"id":92139122,"identity":"5945b3f8-3402-46f4-9d2a-71487784af3f","added_by":"auto","created_at":"2025-09-25 05:12:41","extension":"bbl","order_by":9,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":14439,"visible":true,"origin":"","legend":"","description":"","filename":"snarticle.bbl","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/7cd5a066adb3afabbd81116c.bbl"},{"id":92137777,"identity":"2e1c19f2-b039-4415-83ed-70628dce2d8b","added_by":"auto","created_at":"2025-09-25 05:04:41","extension":"blg","order_by":10,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":2464,"visible":true,"origin":"","legend":"","description":"","filename":"snarticle.blg","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/e07d4a1298d423bc8325a208.blg"},{"id":92137346,"identity":"f032caec-71bb-4440-ab65-d6f2ee45022d","added_by":"auto","created_at":"2025-09-25 04:56:41","extension":"log","order_by":11,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":60777,"visible":true,"origin":"","legend":"","description":"","filename":"snarticle.log","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/424c7ffb629848cc8c539134.log"},{"id":92137347,"identity":"e66784d4-c52d-417f-b099-0fbd7def6012","added_by":"auto","created_at":"2025-09-25 04:56:41","extension":"out","order_by":12,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":1817,"visible":true,"origin":"","legend":"","description":"","filename":"snarticle.out","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/3f192584361408db7ad9bc66.out"},{"id":92137781,"identity":"e46aa994-8b09-4ff3-8efd-31f522b631fc","added_by":"auto","created_at":"2025-09-25 05:04:41","extension":"pdf","order_by":13,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":436202,"visible":true,"origin":"","legend":"","description":"","filename":"snarticle.pdf","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/2f21c4de2362ddae9d9bd97a.pdf"},{"id":92137350,"identity":"74c45914-d94f-4d92-b12a-9745b3dab742","added_by":"auto","created_at":"2025-09-25 04:56:41","extension":"gz","order_by":14,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":150585,"visible":true,"origin":"","legend":"","description":"","filename":"snarticle.synctex.gz","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/a9f6eef4349df9e719a60477.gz"},{"id":92137341,"identity":"dd9f690b-2e62-4772-afb7-0a2988155e36","added_by":"auto","created_at":"2025-09-25 04:56:41","extension":"bst","order_by":15,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":35515,"visible":true,"origin":"","legend":"","description":"","filename":"snbasic.bst","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/d94abfc73212e532ffcda065.bst"},{"id":92137352,"identity":"bdb215e4-600a-442e-813d-df40a900cf68","added_by":"auto","created_at":"2025-09-25 04:56:41","extension":"bst","order_by":16,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":33968,"visible":true,"origin":"","legend":"","description":"","filename":"snchicago.bst","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/87391be5d0344b97479e4d2b.bst"},{"id":92137780,"identity":"57102e5c-fd96-4b6c-84cf-632d38a3a43b","added_by":"auto","created_at":"2025-09-25 05:04:41","extension":"cls","order_by":17,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":55857,"visible":true,"origin":"","legend":"","description":"","filename":"snjnl.cls","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/00d2f5d85383dccca1090631.cls"},{"id":92137783,"identity":"1ad980a5-8778-4ed6-b42a-670262578924","added_by":"auto","created_at":"2025-09-25 05:04:41","extension":"bst","order_by":18,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":64023,"visible":true,"origin":"","legend":"","description":"","filename":"snmathphysay.bst","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/621cafd96c28f632c97cdcf6.bst"},{"id":92137358,"identity":"1f54b4d5-3224-48d4-afb6-dac3dc6e149c","added_by":"auto","created_at":"2025-09-25 04:56:41","extension":"bst","order_by":19,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":64166,"visible":true,"origin":"","legend":"","description":"","filename":"snmathphysnum.bst","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/8b76a6ad4b4213912625e972.bst"},{"id":92137357,"identity":"ac0de76b-72c8-43a3-9348-0cbc7b9a9a53","added_by":"auto","created_at":"2025-09-25 04:56:41","extension":"bst","order_by":20,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":37333,"visible":true,"origin":"","legend":"","description":"","filename":"snnature.bst","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/d158e0ac30d8bad76811f377.bst"},{"id":92137344,"identity":"82bd3598-5879-4585-a356-35e2d56563da","added_by":"auto","created_at":"2025-09-25 04:56:41","extension":"bst","order_by":21,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":39951,"visible":true,"origin":"","legend":"","description":"","filename":"snvancouveray.bst","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/577ea2dfd9781fcf886cc5bf.bst"},{"id":92137348,"identity":"95f71490-e7d5-4798-9df5-cc3f9d8ec790","added_by":"auto","created_at":"2025-09-25 04:56:41","extension":"bst","order_by":22,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":40758,"visible":true,"origin":"","legend":"","description":"","filename":"snvancouvernum.bst","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/fb88ac5938649104609ea842.bst"},{"id":92137359,"identity":"d646c4f8-956b-4fe4-852a-888ab15999e8","added_by":"auto","created_at":"2025-09-25 04:56:41","extension":"pdf","order_by":23,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":418495,"visible":true,"origin":"","legend":"","description":"","filename":"usermanual.pdf","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/dfd66ab2faa66c51f2bfabe7.pdf"},{"id":92137355,"identity":"78c4d53b-01ce-4942-a016-a4ed00211c21","added_by":"auto","created_at":"2025-09-25 04:56:41","extension":"xml","order_by":24,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":109038,"visible":true,"origin":"","legend":"","description":"","filename":"5b6c146e402e4dd8aab02c907b57f7871structuring.xml","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/4699fe610a25702bca81e07e.xml"},{"id":92137356,"identity":"5e53b4d3-1d0a-4ad2-a2c4-9a177f523de8","added_by":"auto","created_at":"2025-09-25 04:56:41","extension":"html","order_by":25,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":131101,"visible":true,"origin":"","legend":"","description":"","filename":"earlyproof.html","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1/e5f88be90b418ecd419a6d18.html"},{"id":96587752,"identity":"7bb56e19-a90c-48df-aba1-c2cc12073867","added_by":"auto","created_at":"2025-11-24 05:23:51","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":304133,"visible":true,"origin":"","legend":"","description":"","filename":"SpringerNatureLaTeXTemplate.pdf","url":"https://assets-eu.researchsquare.com/files/rs-6890100/v1_covered_80798fc9-22db-46b3-adbb-4de437252a5f.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"A Graph-Based Classical and Quantum Approach to Deterministic L-System Inference","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Lindenmayer systems, deterministic L-system inference, maximum independent set, quantum algorithms, QAOA, SAT encoding, formal grammars, symbolic learning","lastPublishedDoi":"10.21203/rs.3.rs-6890100/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-6890100/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eL-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.\u003c/p\u003e","manuscriptTitle":"A Graph-Based Classical and Quantum Approach to Deterministic L-System Inference","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-09-25 04:56:36","doi":"10.21203/rs.3.rs-6890100/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"fce9b277-b467-4638-8fc2-604891a2469f","owner":[],"postedDate":"September 25th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2025-11-24T05:23:42+00:00","versionOfRecord":[],"versionCreatedAt":"2025-09-25 04:56:36","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-6890100","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-6890100","identity":"rs-6890100","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}