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

A $d$-limited automaton is a Turing machine that uses only the cells with theinput word (and end-markers) and rewrites symbols only in the first $d$ visits.This model was introduced by T. Hibbard in 1967 and he showed that $d$-limitedautomata recognize context-free languages for each $d \geq 2$. He also provedthat languages recognizable by deterministic $d$-limited automata form ahierarchy and it was shown later by Pighizzini and Pisoni that it begins withdeterministic context-free languages (DCFLs) (for $d=2$).  As well-known, DCFLs are widely used in practice, especially in compilerssince they are linear-time recognizable and have the corresponding CF-grammarssubclass (LR$(1)$-grammars). In this paper we present a linear time recognitionalgorithm for deterministic $d$-limited automata (in the RAM model) which opensan opportunity for their possible practical applications. We also generalizethis algorithm to deterministic $d(n)$-limited automata: the extension ofdeterministic $d$-limited automata, where $d$ is not a constant, but a functiondepending on the input length $n$.

A Linear-time Simulation of Deterministic $d$-Limited Automata