Succinct representation for (non)deterministic finite automata

DOI10.1016/J.JCSS.2022.07.002MaRDI QIDQ2084735zbMATH OpenOpenAlexFDO

Authors Sankardeep Chakraborty, Roberto Grossi, Kunihiko Sadakane, Srinivasa Rao Satti

Publication date 13 October 2022

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.jcss.2022.07.002

zbMATH Keywords

succinct data structuresencodingdeterministic finite automatatime-space tradeoff

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

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
• Run-Length Encoded Nondeterministic KMP and Suffix Automata
• Compact representations of automata for regular expression matching
• scientific article; zbMATH DE number 1502106

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 5605090 (Why is no real title available?)
• scientific article; zbMATH DE number 2068873 (Why is no real title available?)
• scientific article; zbMATH DE number 7561421 (Why is no real title available?)
• Analytic combinatorics
• Changing base without losing space
• Compact navigation and distance oracles for graphs with small treewidth
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Enumeration and generation with a string automata representation
• Enumeration and random generation of accessible automata
• Exact enumeration of acyclic deterministic automata
• Fully functional static and dynamic succinct trees
• Introduction to algorithms.
• Succinct data structures for families of interval graphs
• Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs
• Succinct encoding of arbitrary graphs
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Succinct representation of balanced parentheses and static trees
• Succinct representations of permutations and functions
• Succinct representations of planar maps
• Wheeler graphs: a framework for BWT-based data structures

Cited in

(5)

• An algorithm for optimal representation of a nondeterministic finite automaton by a set-union knapsack problem
• Efficient evaluation of nondeterministic automata using factorization forests
• Succinct data structure for path graphs
• scientific article; zbMATH DE number 51656 (Why is no real title available?)
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation

This page was built for publication: Succinct representation for (non)deterministic finite automata

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