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 charact...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-05
Main Author: Istrate, Gabriel
Format: Article
Language:English
Subjects:
Permutations
Words (language)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422