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

DOI10.1016/J.IC.2011.03.006zbMATH Open1279.68137OpenAlexW2037649997MaRDI QIDQ418159FDOQ418159

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

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

zbMATH Keywords

stringsbit-parallelismBNDMfactorization of stringsnondeterministic automatonnondeterministic suffix automatonShift-And

Mathematics Subject Classification ID

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

Cites Work

• Efficient randomized pattern-matching algorithms
• A fast string searching algorithm
• Fast Pattern Matching in Strings
• Title not available (Why is that?)
• Fast and flexible string matching by combining bit-parallelism and suffix automata
• Shift-or string matching with super-alphabets
• Multipattern string matching with q -grams
• Alternative algorithms for bit-parallel string matching.

Cited In (14)

• Fast and flexible packed string matching
• A compact representation of nondeterministic (suffix) automata for the bit-parallel approach
• 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
• Linear and Efficient String Matching Algorithms Based on Weak Factor Recognition
• 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

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)