On Parallel Implementations of Deterministic Finite Automata
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F09%3A00159854" target="_blank" >RIV/68407700:21240/09:00159854 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
On Parallel Implementations of Deterministic Finite Automata
Original language description
We present implementations of parallel DFA run methods and find whether and under what conditions is worthy to use the parallel methods of simulation of run of finite automata. First, we introduce the parallel DFA run methods for general DFA, which are universal, but due to the dependency of simulation time on the number of states vertical bar Q vertical bar of automaton being run, they are suitable only for run of automata with the smaller number of states. Then we show that if we apply some restrictions to properties of automata being run, we can reach the linear speedup compared to the sequential simulation method. We designed methods benefiting from k-locality that allows optimum parallel run of exact and approximate pattern matching automata. Finally, we show the results of experiments conducted on two types of parallel computers (Cluster of workstations and Symmetric shared-memory multiprocessors).
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA201%2F09%2F0807" target="_blank" >GA201/09/0807: String and tree analysis and processing</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2009
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Implementation and Application of Automata
ISBN
978-3-642-02978-3
ISSN
0302-9743
e-ISSN
—
Number of pages
11
Pages from-to
—
Publisher name
Springer
Place of publication
Heidelberg
Event location
Sydney
Event date
Jul 14, 2009
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000268667400006