On Arch Factorization and Subword Universality for Words and Compressed Words
From MaRDI portal
Publication:6134881
DOI10.1007/978-3-031-33180-0_21arXiv2304.11932OpenAlexW4381303258MaRDI 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
- Algorithmics on SLP-compressed strings: a survey
- Title not available (Why is that?)
- A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
- Piecewise testable tree languages
- An algorithm for distinguishing efficiently bit-strings by their subsequences
- Title not available (Why is that?)
- Simon's theorem for scattered words
- Deciding Piecewise Testable Separability for Regular Tree Languages
- Title not available (Why is that?)
- Nearly \(k\)-universal words -- investigating a part of Simon's congruence
- Absent subsequences in words
- Title not available (Why is that?)
- Scattered Factor-Universality of Words
- Title not available (Why is that?)
- \(k\)-spectra of weakly-\(c\)-balanced words
- Cutting through regular Post embedding problems
- The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings
- Subsequences in bounded ranges: matching and analysis problems
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)
