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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

A Signed-Winding Dichotomy for Canonical Real-Time Pushdown Realization under Periodic Height Guards

Alp Eren Bütün
Zenodo (CERN European Organization for Nuclear Research)
semigroups and automata theory
preprint

A Signed-Winding Dichotomy for Canonical Real-Time Pushdown Realization under Periodic Height Guards

Alp Eren Bütün
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
semigroups and automata theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon