Achievable high scores of -moves and running times in DPDA computation : (prepublication)
Paul M. B. Vitanyi · Data Archiving and Networked Services (DANS) · 1976
Large scores in the number of consecutive e:-moves a DPDA can make without entering a loop or decreasing its stack below the original stack height are investigated.The achieved scores are very near to an upper bound in the general case and are the upper bound for one-state DPDA's.Upper and lower bounds are derived for the worst case running times of accepting DPDA computations.