A Language-Theoretic Approach to the Heapability of Signed Permutations
<|reference_start|>A Language-Theoretic Approach to the Heapability of Signed Permutations: We investigate a signed version of the Hammersley process, a discrete process on words related to a property of integer sequences called heapability (Byers et al., ANALCO 2011). The specific version that we investigate corresponds to a version of this property for signed sequences.   We give a characterization of the words that can appear as images the signed Hammersley process. In particular we show that the language of such words is the intersection of two deterministic one-counter languages.<|reference_end|>
@article{istrate2024a,
    title={A Language-Theoretic Approach to the Heapability of Signed Permutations},
    author={Gabriel Istrate},
    journal={Proceedings of the Prague Stringology Club (PSC 2024)},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.14275},
    primaryClass={math.CO cs.DM cs.FL}
}