English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In various models of one-way pushdown automata, the explicit use of twodesignated endmarkers on a read-once input tape has proven to be extremelyuseful for making a conscious, final decision on the acceptance/rejection ofeach input word right after reading the right endmarker. With no endmarkers, bycontrast, a machine must constantly stay in either accepting or rejectingstates at any moment since it never notices the end of the input instance. Thissituation, however, helps us analyze the behavior of the machine whose tapehead makes the consecutive moves on all prefixes of a given extremely longinput word. Since those two machine formulations have their own advantages, itis natural to ask whether the endmarkers are truly necessary to correctlyrecognize languages. In the deterministic and nondeterministic models, it iswell-known that the endmarkers are removable without changing the acceptancecriteria of each input instance. This paper proves that, for a more generalmodel of one-way probabilistic pushdown automata, the endmarkers are alsoremovable. This is proven by employing probabilistic transformations from an"endmarker" machine to an equivalent "no-endmarker" machine at the cost ofdouble exponential state complexity without compromising its error probability.By setting this error probability appropriately, our proof also provides analternative proof to both the deterministic and the nondeterministic models aswell.

The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata