On Arch Factorization and Subword Universality for Words and Compressed Words
From MaRDI portal
Publication:6134881
DOI10.1007/978-3-031-33180-0_21OpenAlexW4381303258MaRDI QIDQ6134881FDOQ6134881
Authors: Philippe Schnoebelen 
Publication date: 25 July 2023
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Abstract: Using arch-jumping functions and properties of the arch factorization of words, we propose a new algorithm for computing the subword circular universality index of words. We also introduce the subword universality signature for words, that leads to simple algorithms for the universality indexes of SLP-compressed words.
Full work available at URL: https://arxiv.org/abs/2304.11932
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
- Absent subsequences in words
- Algorithmics on SLP-compressed strings: a survey
- An algorithm for distinguishing efficiently bit-strings by their subsequences
- Deciding piecewise testable separability for regular tree languages
- Nearly \(k\)-universal words -- investigating a part of Simon's congruence
- Piecewise testable tree languages
- Scattered Factor-Universality of Words
- Simon's theorem for scattered words
- Subsequences in bounded ranges: matching and analysis problems
- Testing Simon's congruence
- The ideal approach to computing closed subsets in well-quasi-orderings
- \(k\)-spectra of weakly-\(c\)-balanced words
Cited In (3)
This page was built for publication: On Arch Factorization and Subword Universality for Words and Compressed Words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6134881)
