Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Shortest characteristic factors of a deterministic finite automaton and computing its positive position run by pattern set matching
Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.ORCID-id: 0000-0003-3783-8870
2025 (Engelska)Ingår i: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, Vol. 62, nr 3, artikel-id 36Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

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.

Ort, förlag, år, upplaga, sidor
Springer Nature, 2025. Vol. 62, nr 3, artikel-id 36
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:umu:diva-245641DOI: 10.1007/s00236-025-00484-0ISI: 001567820600001Scopus ID: 2-s2.0-105015587412OAI: oai:DiVA.org:umu-245641DiVA, id: diva2:2006841
Tillgänglig från: 2025-10-16 Skapad: 2025-10-16 Senast uppdaterad: 2025-10-21Bibliografiskt granskad

Open Access i DiVA

fulltext(754 kB)16 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 754 kBChecksumma SHA-512
850affc3103862abc70fb8572e9238e7ed8d00e98254fc6c826f1b7eabf2ee74331126e8e32416c67092c50e79ea70e7fe4c309a1f889f82894303aed8d10dbc
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltextScopus

Person

Plachý, Štěpán

Sök vidare i DiVA

Av författaren/redaktören
Plachý, Štěpán
Av organisationen
Institutionen för datavetenskap
I samma tidskrift
Acta Informatica
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 258 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf