Prague Stringology Conference 2024
A Language-Theoretic Approach to the Heapability of Signed Permutations
| Abstract: |
| 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 of the signed Hammersley process. In particular we show that the language of such words is the intersection of two deterministic one-counter languages. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |