Cyclic Equalizability Characterized by Parikh Vectors

• URL: http://arxiv.org/abs/2604.19504v1
• Date: Tue, 21 Apr 2026 14:22:19 GMT
• Title: Cyclic Equalizability Characterized by Parikh Vectors
• Abstract summary: Cyclic equalizability is a notion introduced by Shinagawa and Nuida in 2025.<n>We prove that two words are cyclically equalizable if and only if they have the same Parikh vector.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cyclic equalizability is a notion introduced by Shinagawa and Nuida in 2025, in the study of card-based cryptography. Informally, a collection of words is cyclically equalizable if, by inserting the same letters at the same positions in all words, they can be transformed into words that are cyclic shifts of one another. Shinagawa and Nuida showed that two binary words of equal length are cyclically equalizable if and only if they have the same Hamming weight. They also posed the problem of characterizing cyclic equalizability over larger alphabets. In this paper, we completely characterize cyclic equalizability for two words over an arbitrary finite alphabet by proving that two words are cyclically equalizable if and only if they have the same Parikh vector.

Related papers

• 0-Cyclic Equalizability of Binary Words Characterized by Hamming Weight [0.0]
  Two binary words of equal length are 0-cyclically equalizable if and only if they have equal Hamming weight.<n>We encode a pair of binary words as a single word over the four-letter alphabet A, B, X, O.
  arXiv  Detail & Related papers  (2026-07-20T19:02:48Z)
• Flashback: A Reversible Bilateral Run-Peeling Decomposition of Strings [0.0]
  Flashback is a reversible string decomposition that repeatedly peels the maximal leading and trailing character runs from a sentinel-wrapped input.<n>Our central result is a run-pairing theorem: Flashback is equivalent to pairing the first run of the string with the last, the second with the second-to-last, and so on.<n>This gives an exact token count of 1+[r/2] for a string with r maximal runs, and matches a lower bound that holds for any admissible bilateral run-peeling scheme.
  arXiv  Detail & Related papers  (2026-04-29T00:30:33Z)
• Random Text, Zipf's Law, Critical Length,and Implications for Large Language Models [0.0]
  We study a deliberately simple, fully non-linguistic model of text.<n>A word is defined as a maximal block of non-space symbols.
  arXiv  Detail & Related papers  (2025-11-14T23:05:59Z)
• Cyclic Equalizability of Words and Its Application to Card-Based Cryptography [0.36832029288386137]
  We show that two binary words of equal length and equal Hamming weight are cyclically equalizable.<n>As applications of cyclic equalizability to card-based cryptography, we describe its applications to the information erasure problem and to single-cut full-open protocols.
  arXiv  Detail & Related papers  (2025-07-07T12:03:36Z)
• On Affine Homotopy between Language Encoders [127.55969928213248]
  We study the properties of emphaffine alignment of language encoders.<n>We find that while affine alignment is fundamentally an asymmetric notion of similarity, it is still informative of extrinsic similarity.
  arXiv  Detail & Related papers  (2024-06-04T13:58:28Z)
• Sub-Sentence Encoder: Contrastive Learning of Propositional Semantic Representations [102.05351905494277]
  Sub-sentence encoder is a contrastively-learned contextual embedding model for fine-grained semantic representation of text. We show that sub-sentence encoders keep the same level of inference cost and space complexity compared to sentence encoders.
  arXiv  Detail & Related papers  (2023-11-07T20:38:30Z)
• $\alpha$-$\beta$-Factorization and the Binary Case of Simon's Congruence [1.5935205681539144]
  In 1991 H'ebrard introduced a factorization of words that turned out to be a powerful tool for the investigation of a word's scattered factors. Based on this, first Karandikar and Schnoebelen introduced the notion of $k$-richness and later on Barker et al. the notion of $k$-universality. In 2022 Fleischmann et al. presented a generalization of the arch factorization by intersecting the arch factorization of a word and its reverse.
  arXiv  Detail & Related papers  (2023-06-25T10:16:49Z)
• Compositional Generalization without Trees using Multiset Tagging and Latent Permutations [121.37328648951993]
  We phrase semantic parsing as a two-step process: we first tag each input token with a multiset of output tokens. Then we arrange the tokens into an output sequence using a new way of parameterizing and predicting permutations. Our model outperforms pretrained seq2seq models and prior work on realistic semantic parsing tasks.
  arXiv  Detail & Related papers  (2023-05-26T14:09:35Z)
• Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective [97.57162770792182]
  Tasks that model the relation between pairs of tokens in a string are a vital part of understanding natural language. We show that these exhaustive comparisons can be avoided, and, moreover, the complexity can be reduced to linear by casting the relation between tokens as a partial order over the string. Our method predicts real numbers for each token in a string in parallel and sorts the tokens accordingly, resulting in total orders of the tokens in the string.
  arXiv  Detail & Related papers  (2023-05-24T11:47:35Z)
• Comment on "Strong Quantum Darwinism and Strong Independence are Equivalent to Spectrum Broadcast Structure" [62.997667081978825]
  We show that the mathematical formulation of condition (b) is necessary but not sufficient to ensure the equivalence. We propose a simple counter-example, together with a strengthened formulation of condition (b)
  arXiv  Detail & Related papers  (2021-01-21T16:06:25Z)
• Span-based Semantic Parsing for Compositional Generalization [53.24255235340056]
  SpanBasedSP predicts a span tree over an input utterance, explicitly encoding how partial programs compose over spans in the input. On GeoQuery, SCAN and CLOSURE, SpanBasedSP performs similarly to strong seq2seq baselines on random splits, but dramatically improves performance compared to baselines on splits that require compositional generalization.
  arXiv  Detail & Related papers  (2020-09-13T16:42:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.