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

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F24%3A00381708" target="_blank" >RIV/68407700:21240/24:00381708 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-031-52113-3_23" target="_blank" >https://doi.org/10.1007/978-3-031-52113-3_23</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-52113-3_23" target="_blank" >10.1007/978-3-031-52113-3_23</a>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

Given a deterministic finite automaton (DFA) A, we present a simple algorithm for constructing four deterministic finite automata that accept the shortest forbidden factors, the shortest forbidden suffixes, the shortest allowed suffixes, and the shortest forbidden prefixes. We refer to these automata as the shortest characteristic factors of 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 four automata are acyclic. This approach simplifies existing methods for the extraction of forbidden factors and also generalizes it for all classes of input 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 allowed suffixes, provided that the sets are finite. We showcase the computation of the positive position run of a local automaton using backward pattern matching, which can achieve sublinear time.

Název v anglickém jazyce

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

Popis výsledku anglicky

Given a deterministic finite automaton (DFA) A, we present a simple algorithm for constructing four deterministic finite automata that accept the shortest forbidden factors, the shortest forbidden suffixes, the shortest allowed suffixes, and the shortest forbidden prefixes. We refer to these automata as the shortest characteristic factors of 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 four automata are acyclic. This approach simplifies existing methods for the extraction of forbidden factors and also generalizes it for all classes of input 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 allowed suffixes, provided that the sets are finite. We showcase the computation of the positive position run of a local automaton using backward pattern matching, which can achieve sublinear time.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

SOFSEM 2024: Theory and Practice of Computer Science

ISBN

978-3-031-52112-6

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

14

Strana od-do

326-339

Název nakladatele

Springer, Cham

Místo vydání

—

Místo konání akce

Cochem

Datum konání akce

19. 2. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001206989000023