A compact representation of nondeterministic (suffix) automata for the bit-parallel approach

DOI10.1016/J.IC.2011.03.006MaRDI QIDQ418159zbMATH OpenOpenAlexFDO

Authors Domenico Cantone, Simone Faro, Emanuele Giaquinta

Publication date 24 May 2012

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2011.03.006

zbMATH Keywords

stringsbit-parallelismBNDMfactorization of stringsnondeterministic automatonnondeterministic suffix automatonShift-And

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithms on strings (68W32)

Recommendations

• A compact representation of nondeterministic (suffix) automata for the bit-parallel approach
• Run-Length Encoded Nondeterministic KMP and Suffix Automata
• On the bit-parallel simulation of the nondeterministic Aho-Corasick and suffix automata for a set of patterns
• A New Approach to Determinisation Using Bit-Parallelism
• A SPACE EFFICIENT BIT-PARALLEL ALGORITHM FOR THE MULTIPLE STRING MATCHING PROBLEM

Cites work

• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• A fast string searching algorithm
• Alternative algorithms for bit-parallel string matching.
• Efficient randomized pattern-matching algorithms
• Fast Pattern Matching in Strings
• Fast and flexible string matching by combining bit-parallelism and suffix automata
• Multipattern string matching with q -grams
• Shift-or string matching with super-alphabets

Cited in

(15)

• Fast and flexible packed string matching
• A compact representation of nondeterministic (suffix) automata for the bit-parallel approach
• Linear and efficient string matching algorithms based on weak factor recognition
• On a compact encoding of the swap automaton
• On the bit-parallel simulation of the nondeterministic Aho-Corasick and suffix automata for a set of patterns
• From nondeterministic suffix automaton to lazy suffix tree
• Efficient string matching based on a two-step simulation of the suffix automaton
• The Range Automaton: an efficient approach to text-searching
• Run-Length Encoded Nondeterministic KMP and Suffix Automata
• A New Approach to Determinisation Using Bit-Parallelism
• A weak approach to suffix automata simulation for exact and approximate string matching
• A very fast string matching algorithm based on condensed alphabets
• A SPACE EFFICIENT BIT-PARALLEL ALGORITHM FOR THE MULTIPLE STRING MATCHING PROBLEM
• Compact suffix automata representations for searching long patterns
• Succinct representation for (non)deterministic finite automata

This page was built for publication: A compact representation of nondeterministic (suffix) automata for the bit-parallel approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q418159)