Image de couverture de livre

Encoding Co-Lex Orders of Finite-State Automata in Linear Space

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Becker, Ruben, Cotumaccio, Nicola, Kim, Sung-Hwan, Prezza, Nicola, Tosoni, Carlo
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Indexing Finite-State Automata Using Forward-Stable Partitions
par: Becker, Ruben, et autres
Publié: (2024)

Random Wheeler Automata
par: Becker, Ruben, et autres
Publié: (2023)

Space-time Trade-offs for the LCP Array of Wheeler DFAs
par: Cotumaccio, Nicola, et autres
Publié: (2023)

Computing the LCP Array of a Labeled Graph
par: Alanko, Jarno, et autres
Publié: (2024)

A Myhill-Nerode Theorem for Generalized Automata, with Applications to Pattern Matching and Compression
par: Cotumaccio, Nicola
Publié: (2023)

Improved Circular Dictionary Matching
par: Cotumaccio, Nicola
Publié: (2025)

Fast Pattern Matching with Epsilon Transitions
par: Cotumaccio, Nicola
Publié: (2025)

Enhanced Graph Pattern Matching
par: Cotumaccio, Nicola
Publié: (2024)

Sketching and Streaming for Dictionary Compression
par: Becker, Ruben, et autres
Publié: (2023)

Algorithms for Massive Data -- Lecture Notes
par: Prezza, Nicola
Publié: (2023)

Linear Space Streaming Lower Bounds for Approximating CSPs
par: Chou, Chi-Ning, et autres
Publié: (2021)

The Trie Measure, Revisited
par: Alanko, Jarno N., et autres
Publié: (2025)

Compressing Suffix Trees by Path Decompositions
par: Becker, Ruben, et autres
Publié: (2025)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
par: Sajith, Thejas Radhika
Publié: (2025)

Self-referential instances of the dominating set problem are irreducible
par: Zhou, Guangyan
Publié: (2026)

Wheeler Bisimulations
par: Cotumaccio, Nicola
Publié: (2026)

Solving Polynomial Equations Over Finite Fields
par: Dell, Holger, et autres
Publié: (2024)

Linear Hashing Is Optimal
par: Jaber, Michael, et autres
Publié: (2025)

On Optimal Testing of Linearity
par: Arora, Vipul, et autres
Publié: (2024)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
par: Wang, Chengu
Publié: (2026)

On the Space Complexity of Online Convolution
par: Andersson, Joel Daniel, et autres
Publié: (2025)

The Structure of In-Place Space-Bounded Computation
par: Cook, James, et autres
Publié: (2025)

Improved Space Bounds for Subset Sum
par: Belova, Tatiana, et autres
Publié: (2024)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
par: Rohwedder, Lars, et autres
Publié: (2024)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
par: Greilhuber, Jakob, et autres
Publié: (2026)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
par: Jansen, Bart M. P., et autres
Publié: (2026)

Gray Codes With Constant Delay and Constant Auxiliary Space
par: Amarilli, Antoine, et autres
Publié: (2026)

Near-Optimal Space Lower Bounds for Streaming CSPs
par: Fei, Yumou, et autres
Publié: (2026)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
par: Jiang, Cheng, et autres
Publié: (2026)

A Space-space Trade-off for Directed st-Connectivity
par: Edenhofer, Roman
Publié: (2026)

Frontier Space-Time Algorithms Using Only Full Memory
par: Chmel, Petr, et autres
Publié: (2026)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
par: Grossman, Ofer, et autres
Publié: (2023)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
par: Shih, Yu-Sheng, et autres
Publié: (2026)

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
par: Asadi, Vahid R., et autres
Publié: (2026)

Suffixient Arrays: a New Efficient Suffix Array Compression Technique
par: Cenzato, Davide, et autres
Publié: (2024)

Testing Suffixient Sets
par: Cenzato, Davide, et autres
Publié: (2025)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
par: Kim, Eun Jung, et autres
Publié: (2022)

Bandwidth Parameterized by Cluster Vertex Deletion Number
par: Gima, Tatsuya, et autres
Publié: (2023)

Indexing Tries within Entropy-Bounded Space
par: Carfagna, Lorenzo, et autres
Publié: (2025)

Lower Bounds for Linear Operators
par: Ko, Young Kun
Publié: (2025)