Exact Pareto Corners and Uniform State–Stack Tradeoffs in a Binary Deterministic Pushdown Hierarchy

The paper extends our binary deterministic pushdown-automaton hierarchy from individual state or stack-alphabet lower bounds to the joint geometry of the two physical resources. For the witness languages Bm,k, it studies which pairs of control-state counts and stack-alphabet sizes are Pareto-minimal under a specified deterministic model allowing epsilon moves and arbitrary finite stack replacements, with a single initial stack symbol and final-state-plus-empty-stack acceptance. It proves exact Pareto corner families, sharp resource thresholds on explicit parameter ranges, and an exact one-state stack-alphabet threshold. Beyond particular constructions, it establishes uniform upper and lower bounds showing that the number of Pareto points grows on the order of the square root of mk, and identifies a region in which every state budget from 1 through m occurs as a distinct Pareto coordinate. Its main novelty is turning state–stack recoding and resource lower bounds into quantitative results about the width, support, and exact corners of a genuine two-resource Pareto frontier. The full frontier for arbitrary parameters remains open.