A Signed-Winding Dichotomy for Canonical Real-Time Pushdown Realization under Periodic Height Guards
The paper extends our linear modular height-guard classification to arbitrary explicitly specified rectangularly periodic constraints on two independent tagged Dyck-prefix stacks. Rather than restricting the allowed height pairs to a single modular linear condition, it analyzes the signed displacement structure of connected components in a finite periodic quotient graph. It proves an exact necessary-and-sufficient criterion: the guarded language is context-free, and admits a canonical deterministic real-time one-stack realization preserving both complete source stacks, precisely when every component has either zero winding rank or rank-one winding with nonnegative coordinate product. Rank-two components necessarily produce crossed-equality obstructions, while negatively sloped rank-one components produce three-equal-block obstructions, establishing non-context-freeness in every excluded case. The criterion is decidable in linear word-RAM time in the size of the explicitly represented mask, and the positive constructions preserve source-action enabledness without epsilon transitions. Its main novelty is the finite signed-winding characterization that turns a geometric classification of periodic height constraints into an exact equivalence between context-freeness and source-faithful real-time realizability, substantially generalizing the preceding linear modular result without claiming a classification of arbitrary semilinear guards.
Authors
- Alp Eren Bütün
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-10-31
- DOI
- https://doi.org/10.5281/zenodo.23842967
- Primary Topic
- semigroups and automata theory
- Type
- preprint