Succinct representation for (non)deterministic finite automata
From MaRDI portal
Publication:2084735
DOI10.1016/J.JCSS.2022.07.002zbMATH Open1497.68254OpenAlexW4290794100MaRDI QIDQ2084735FDOQ2084735
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)
Full work available at URL: https://doi.org/10.1016/j.jcss.2022.07.002
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
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)
Cites Work
- Analytic combinatorics
- Introduction to algorithms.
- Succinct representation of balanced parentheses and static trees
- Fully functional static and dynamic succinct trees
- Dynamic Perfect Hashing: Upper and Lower Bounds
- Title not available (Why is that?)
- Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
- Succinct encoding of arbitrary graphs
- Title not available (Why is that?)
- Enumeration and random generation of accessible automata
- Enumeration and generation with a string automata representation
- Succinct representations of permutations and functions
- Succinct representations of planar maps
- Exact enumeration of acyclic deterministic automata
- Changing base without losing space
- Compact navigation and distance oracles for graphs with small treewidth
- Wheeler graphs: a framework for BWT-based data structures
- Succinct data structures for families of interval graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs
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
- Title not available (Why is that?)
- 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)
