Run-Length Encoded Nondeterministic KMP and Suffix Automata

DOI10.1007/978-3-319-22360-5_9MaRDI QIDQ2947413zbMATH OpenOpenAlexFDO

Authors Emanuele Giaquinta

Publication date 23 September 2015

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.3688

Mathematics Subject Classification ID

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

Abstract: We present a novel bit-parallel representation, based on the run-length encoding, of the nondeterministic KMP and suffix automata for a string $P$ with at least two distinct symbols. Our method is targeted to the case of long strings over small alphabets and complements the method of Cantone et al. (2012), which is effective for long strings over large alphabets. Our encoding requires $O((sigma+m)lceilho/wceil)$ space and allows one to simulate the automata on a string in time $O(lceilho/wceil)$ per transition, where $sigma$ is the alphabet size, $m$ is the length of $P$, $ho$ is the length of the run-length encoding of $P$ and $w$ is the machine word size in bits. The input string can be given in either unencoded or run-length encoded form.

Recommendations

• A compact representation of nondeterministic (suffix) automata for the bit-parallel approach
• A compact representation of nondeterministic (suffix) automata for the bit-parallel approach
• scientific article; zbMATH DE number 3972192
• Extended nondeterministic finite automata
• Succinct representations for (non)deterministic finite automata
• Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• Non-deterministic finite cover automata
• Nondeterministic state complexity for suffix-free regular languages
• General suffix automaton construction algorithm and space bounds

Cites work

• A compact representation of nondeterministic (suffix) automata for the bit-parallel approach
• Alternative algorithms for bit-parallel string matching.
• Average-optimal string matching
• Bit-parallel witnesses and their applications to approximate string matching
• Efficient pattern matching with scaling
• Fast and flexible string matching by combining bit-parallelism and suffix automata
• Fast Pattern Matching in Strings
• Faster approximate string matching
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1754502 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• Improving practical exact string matching
• Improving the bit-parallel NFA of Baeza-Yates and Navarro for approximate string matching
• On a compact encoding of the swap automaton

Cited in

(5)

• Succinct representation for (non)deterministic finite automata
• From nondeterministic suffix automaton to lazy suffix tree
• A compact representation of nondeterministic (suffix) automata for the bit-parallel approach
• On the bit-parallel simulation of the nondeterministic Aho-Corasick and suffix automata for a set of patterns
• A compact representation of nondeterministic (suffix) automata for the bit-parallel approach

This page was built for publication: Run-Length Encoded Nondeterministic KMP and Suffix Automata

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