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

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2024

Confidentiality

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

Article name in the collection

SOFSEM 2024: Theory and Practice of Computer Science

ISBN

978-3-031-52112-6

ISSN

0302-9743

e-ISSN

—

Number of pages

14

Pages from-to

326-339

Publisher name

Springer, Cham

Place of publication

—

Event location

Cochem

Event date

Feb 19, 2024

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

001206989000023