✦ LIBER ✦

Families of automata characterizing context-sensitive languages

✍ Scribed by Christophe Morvan; Chloé Rispal

Publisher: Springer-Verlag
Year: 2005
Tongue: English
Weight: 238 KB
Volume: 41
Category: Article
ISSN: 0001-5903
DOI: 10.1007/s00236-004-0160-0

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A note on multihead automata and context

A note on multihead automata and context-sensitive languages

✍ Walter J. Savitch 📂 Article 📅 1973 🏛 Springer-Verlag 🌐 English ⚖ 204 KB

Deque automata and a subfamily of contex

Deque automata and a subfamily of context-sensitive languages which contains all semilinear bounded languages

✍ Kathleen Ayers 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 652 KB

A generator of context-sensitive languag

A generator of context-sensitive languages

✍ Ben Wegbreit 📂 Article 📅 1969 🏛 Elsevier Science 🌐 English ⚖ 252 KB

The existence of a context-sensitive grammar, G~, which acts as a "generator" of all context-sensitive languages is established. Specifically, G~ has the property that for each context-sensitive language, L, there exists a regular set, RL, and an e-limited gsm, gL, such that L = gz(L(G,,) ~ .RL). It

Dm-automata and classes of context-free

Dm-automata and classes of context-free languages

✍ A. B. Stavrovskii; O. Yu. Pavliv 📂 Article 📅 1993 🏛 Springer US 🌐 English ⚖ 520 KB

One-way globally deterministic synchroni

One-way globally deterministic synchronized alternating finite automata recognize exactly deterministic context-sensitive languages

✍ Anna Slobodová 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 400 KB

Growth-sensitivity of context-free langu

Growth-sensitivity of context-free languages

✍ Tullio Ceccherini-Silberstein; Wolfgang Woess 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 265 KB

A language L over a ÿnite alphabet is called growth-sensitive if forbidding any set of subwords F yields a sub-language L F whose exponential growth rate is smaller than that of L. It is shown that every (essentially) ergodic non-linear context-free language of convergent type is growth-sensitive. "