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

We study the expressiveness and succinctness of history-deterministicpushdown automata (HD-PDA) over finite words, that is, pushdown automata whosenondeterminism can be resolved based on the run constructed so far, butindependently of the remainder of the input word. These are also known asgood-for-games pushdown automata. We prove that HD-PDA recognise more languagesthan deterministic PDA (DPDA) but not all context-free languages (CFL). Thisclass is orthogonal to unambiguous CFL. We further show that HD-PDA can beexponentially more succinct than DPDA, while PDA can be double-exponentiallymore succinct than HD-PDA. We also study HDness in visibly pushdown automata(VPA), which enjoy better closure properties than PDA, and for which we showthat deciding HDness is ExpTime-complete. HD-VPA can be exponentially moresuccinct than deterministic VPA, while VPA can be exponentially more succinctthan HD-VPA. Both of these lower bounds are tight. We then compare HD-PDA withPDA for which composition with games is well-behaved, i.e. good-for-gamesautomata. We show that these two notions coincide, but only if we considerpotentially infinitely branching games. Finally, we study the complexity ofresolving nondeterminism in HD-PDA. Every HDPDA has a positional resolver, afunction that resolves nondeterminism and that is only dependant on the currentconfiguration. Pushdown transducers are sufficient to implement the resolversof HD-VPA, but not those of HD-PDA. HD-PDA with finite-state resolvers aredeterminisable.

A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct