arXiv preprint ·
Jumbled Simon's Equivalence and Embeddings
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
\emph{Jumbled scattered factors} are a generalisation of scattered factors (or subsequences) where a jumbled scattered factor is obtained from another word by deleting and rearranging letters. For limiting the number of rearrangements, we distinguish $\ell$-jumbled scattered factors where $\ell$ limits the number of letters that may occur rearranged. For instance, $\mathtt{car}$, $\mathtt{start}$, $\mathtt{rat}, \mathtt{cat}$ are jumbled scattered factors of $\mathtt{abstract}$ even though $\mathtt{car}$, $\mathtt{start}$ and $\mathtt{cat}$ are no scattered factors and each need one jumble. An example for a jumbled scattered factor with $2$ jumbles is $\mathtt{tatar}$. In this work, we investigate two problems on jumbled scattered factors from an algorithmic perspective. First, we give algorithms for testing jumbled Simon's equivalence where two words are equivalent if they share the same $\ell$-jumbled scattered factors up to length $k$. Second, we investigate how to count the possible occurrences of a jumbled scattered factor -- the jumbled binomial coefficient. After defining the jumbled binomial coefficient, we study jumbled embeddings and factorisations of such as well.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Formal Languages & Automata
At the Limits of Computability: Steps Towards Autonomous AI Discovery on the Busy Beaver Frontier
Limit-sure Winning in Team Games without Shared Randomness
On the Complexity of Level-Synchronized Tree Automata for Quantum Circuit Verification
Type-Checking for Pattern-Based Tree Transformations
Reward Objectives for Robust (PO)MDPs: A Law-Preserving Equivalence with (Partially Observable) Games
Get the few papers worth your time in Formal Languages & Automata every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.