Shortest Characteristic Factors of a Deterministic Finite Automaton and Computing Its Positive Position Run by Pattern Set Matching

Shortest Characteristic Factors of a Deterministic Finite Automaton and Computing Its Positive Position Run by Pattern Set Matching | 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 Shortest Characteristic Factors of a Deterministic Finite Automaton and Computing Its Positive Position Run by Pattern Set Matching Jan Janoušek, Štěpán Plachý This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-4358862/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 10 Sep, 2025 Read the published version in Acta Informatica → Version 1 posted 9 You are reading this latest preprint version Abstract Given a deterministic finite automaton (DFA) A, we present a simple algorithm for constructing deterministic finite automata that accept the shortest forbidden factors, the shortest forbidden prefixes, the shortest forbidden suffixes, the shortest forbidden words, the shortest allowed suffixes, and the shortest allowed words of the automaton A. We refer to these sets as the shortest characteristic factors of the automaton A. If the given automaton is local, and therefore the language it accepts is strictly locally testable, the sets of its shortest characteristic factors are finite, and these automata are acyclic. Otherwise, they accept infinite languages. This approach simplifies existing methods for the extraction of forbidden factors, allows the extraction of more types of characteristic factors, and also generalizes the extraction for all classes of DFAs. Furthermore, we demonstrate that this type of extraction can be used for a sublinear run of an automaton for certain inputs. We define a positive position run of a deterministic finite automaton, representing all positions in an input string where the automaton reaches a final state. Finally, we present an algorithm for computing the positive position run of the automaton, which utilizes pattern set matching of its shortest forbidden factors and its shortest forbidden or allowed suffixes, provided that the sets are finite. We showcase the computation of the positive position run of a local automaton using backward pattern set matching, which can achieve sublinear time. Finite automata Local finite automata Shortest characteristic factors Strictly locally testable languages Pattern matching Positive position run of automata Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 10 Sep, 2025 Read the published version in Acta Informatica → Version 1 posted Editorial decision: Revision requested 05 Aug, 2024 Reviews received at journal 05 Aug, 2024 Reviews received at journal 05 Aug, 2024 Reviewers agreed at journal 09 May, 2024 Reviewers agreed at journal 09 May, 2024 Reviewers invited by journal 06 May, 2024 Submission checks completed at journal 02 May, 2024 Editor assigned by journal 02 May, 2024 First submitted to journal 02 May, 2024 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-4358862","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":299380116,"identity":"baeb279d-51c5-4ad0-a261-96f7c6903f78","order_by":0,"name":"Jan Janoušek","email":"","orcid":"","institution":"Czech Technical University in Prague","correspondingAuthor":false,"prefix":"","firstName":"Jan","middleName":"","lastName":"Janoušek","suffix":""},{"id":299380117,"identity":"bc1ab061-5de7-4899-82a0-81ed3dd099de","order_by":1,"name":"Štěpán Plachý","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABDklEQVRIie3RMUsDMRQH8HcevC5Jb0059b5CjoNzOehXiQh18QM4CK0cxMm9w+HHKI7CQaZ+iJZCpnOVCgrmkhYFSbsK5r8kw/uR914AQkL+YLKZO6dDAAS4PSdHCVfuvJSWLAvijDhA8CeJZAHHSVar1fuzIYNWb+gTPx1DrFO6hWzf869ZJF7nj0uYIplcFHTBTWNYpkRAfu8hoEjJqASBcIMpXXwYQuLCEBH7OlPJ2+izJ0lnSMO/CXoJMZU9Yf0rM0uiTU986+bKjHAmmSG6HDXKkBbzdTNh+dxDsrrV61dZiSS50qy74+PBQ7166arKuzGwPwjM3k5sL25s5q3fEZdoe6guJCQk5N/mC3cpRAWcuZl+AAAAAElFTkSuQmCC","orcid":"","institution":"Czech Technical University in Prague","correspondingAuthor":true,"prefix":"","firstName":"Štěpán","middleName":"","lastName":"Plachý","suffix":""}],"badges":[],"createdAt":"2024-05-02 11:28:35","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-4358862/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-4358862/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1007/s00236-025-00484-0","type":"published","date":"2025-09-10T15:57:19+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":91359000,"identity":"effd69c3-4eb1-4c77-960e-d4b274b30f35","added_by":"auto","created_at":"2025-09-15 16:03:54","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":433939,"visible":true,"origin":"","legend":"","description":"","filename":"charfactors.pdf","url":"https://assets-eu.researchsquare.com/files/rs-4358862/v1_covered_2461fd54-43b7-46a7-a5e3-64f6bcbe87b1.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Shortest Characteristic Factors of a Deterministic Finite Automaton and Computing Its Positive Position Run by Pattern Set Matching","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"acta-informatica","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"acin","sideBox":"Learn more about [Acta Informatica](http://link.springer.com/journal/236)","snPcode":"236","submissionUrl":"https://submission.nature.com/new-submission/236/3","title":"Acta Informatica","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"Finite automata, Local finite automata, Shortest characteristic factors, Strictly locally testable languages, Pattern matching, Positive position run of automata","lastPublishedDoi":"10.21203/rs.3.rs-4358862/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-4358862/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Given a deterministic finite automaton (DFA) A, we present a simple algorithm for constructing deterministic finite automata that accept the shortest forbidden factors, the shortest forbidden prefixes, the shortest forbidden suffixes, the shortest forbidden words, the shortest allowed suffixes, and the shortest allowed words of the automaton A. We refer to these sets as the shortest characteristic factors of the automaton A. If the given automaton is local, and therefore the language it accepts is strictly locally testable, the sets of its shortest characteristic factors are finite, and these automata are acyclic. Otherwise, they accept infinite languages. This approach simplifies existing methods for the extraction of forbidden factors, allows the extraction of more types of characteristic factors, and also generalizes the extraction for all classes of DFAs. Furthermore, we demonstrate that this type of extraction can be used for a sublinear run of an automaton for certain inputs. We define a positive position run of a deterministic finite automaton, representing all positions in an input string where the automaton reaches a final state. Finally, we present an algorithm for computing the positive position run of the automaton, which utilizes pattern set matching of its shortest forbidden factors and its shortest forbidden or allowed suffixes, provided that the sets are finite. We showcase the computation of the positive position run of a local automaton using backward pattern set matching, which can achieve sublinear time.","manuscriptTitle":"Shortest Characteristic Factors of a Deterministic Finite Automaton and Computing Its Positive Position Run by Pattern Set Matching","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-05-08 05:18:24","doi":"10.21203/rs.3.rs-4358862/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2024-08-05T20:00:53+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2024-08-05T17:57:24+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2024-08-05T04:14:43+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"279629119674731249693647486233340449273","date":"2024-05-09T21:16:10+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"214782569148538492643053458247197869453","date":"2024-05-09T13:58:06+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2024-05-06T18:09:34+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-05-02T14:12:17+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2024-05-02T14:12:17+00:00","index":"","fulltext":""},{"type":"submitted","content":"Acta Informatica","date":"2024-05-02T11:27:17+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"acta-informatica","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"acin","sideBox":"Learn more about [Acta Informatica](http://link.springer.com/journal/236)","snPcode":"236","submissionUrl":"https://submission.nature.com/new-submission/236/3","title":"Acta Informatica","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"3bfe2ba8-d6b2-432e-9dc1-6d6ea08bef90","owner":[],"postedDate":"May 8th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2025-09-15T15:59:46+00:00","versionOfRecord":{"articleIdentity":"rs-4358862","link":"https://doi.org/10.1007/s00236-025-00484-0","journal":{"identity":"acta-informatica","isVorOnly":false,"title":"Acta Informatica"},"publishedOn":"2025-09-10 15:57:19","publishedOnDateReadable":"September 10th, 2025"},"versionCreatedAt":"2024-05-08 05:18:24","video":"","vorDoi":"10.1007/s00236-025-00484-0","vorDoiUrl":"https://doi.org/10.1007/s00236-025-00484-0","workflowStages":[]},"version":"v1","identity":"rs-4358862","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-4358862","identity":"rs-4358862","version":["v1"]},"buildId":"qtupq5eGEP_6zYnWcrvyt","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}