On Arch Factorization and Subword Universality for Words and Compressed Words

DOI10.1007/978-3-031-33180-0_21MaRDI QIDQ6134881zbMATH OpenOpenAlexFDO

Authors Philippe Schnoebelen

Publication date 25 July 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2304.11932

Mathematics Subject Classification ID

Combinatorics on words (68R15)

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.

Cites work

• \(k\)-spectra of weakly-\(c\)-balanced words
• 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
• scientific article; zbMATH DE number 3495598 (Why is no real title available?)
• scientific article; zbMATH DE number 2051146 (Why is no real title available?)
• scientific article; zbMATH DE number 7297889 (Why is no real title available?)
• scientific article; zbMATH DE number 7056230 (Why is no real title available?)
• 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

Cited in

(10)

• Existential Definability over the Subword Ordering
• Simon's congruence pattern matching
• Matching patterns with variables under Simon's congruence
• Jumbled scattered factors
• k-universality of regular languages
• Subsequences with generalised gap constraints: upper and lower complexity bounds
• k-universality of regular languages revisited
• \(k\)-universality of regular languages
• Subsequence matching and analysis problems for formal languages
• Title not available (Why is no real title available?)

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)