Faster Generation of Super Condensed Neighbourhoods Using Finite Automata | Zendy

Luís M. S.​Russo | Zendy; Arlindo L. Oliveira | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Faster Generation of Super Condensed Neighbourhoods Using Finite Automata

Author(s) -

Luís M. S.Russo,

Arlindo L. Oliveira

Publication year - 2005

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-29740-5

DOI - 10.1007/11575832_28

Subject(s) - automaton , computer science , neighbourhood (mathematics) , parallelism (grammar) , string searching algorithm , string (physics) , set (abstract data type) , matching (statistics) , cellular automaton , theoretical computer science , algorithm , pattern matching , parallel computing , mathematics , programming language , mathematical analysis , statistics , mathematical physics

We present a new algorithm for generating super condensed neighbourhoods. Super condensed neighbourhoods have recently been presented as the minimal set of words that represent a pattern neighbourhood. These sets play an important role in the generation phase of hybrid algorithms for indexed approximate string matching. An existing algorithm for this purpose is based on a dynamic programming approach, implemented using bit-parallelism. In this work we present a bit-parallel algorithm based on automata which is faster, conceptually much simpler and uses less memory than the existing method.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research