Succinct representation for (non)deterministic finite automata

DOI10.1016/j.jcss.2022.07.002zbMath1497.68254OpenAlexW4290794100MaRDI QIDQ2084735

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

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

zbMATH Keywords

deterministic finite automatatime-space tradeoffencodingsuccinct data structures

Mathematics Subject Classification ID

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

Related Items (1)

Succinct data structure for path graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Succinct encoding of arbitrary graphs
• Succinct representations of permutations and functions
• Compact navigation and distance oracles for graphs with small treewidth
• Succinct representations of planar maps
• Enumeration and random generation of accessible automata
• Wheeler graphs: a framework for BWT-based data structures
• Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs
• Succinct data structures for families of interval graphs
• Enumeration and generation with a string automata representation
• Exact enumeration of acyclic deterministic automata
• Succinct Representation of Balanced Parentheses and Static Trees
• Fully Functional Static and Dynamic Succinct Trees
• Changing base without losing space
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets

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