𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Some algorithmic problems for groups and context-free languages

✍ Scribed by A. V. Anisimov

Publisher
Springer US
Year
1974
Tongue
English
Weight
861 KB
Volume
8
Category
Article
ISSN
1573-8337

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The inclusion problem for some subclasse
The inclusion problem for some subclasses of context-free languages
✍ Peter R.J. Asveld; Anton Nijholt πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 131 KB

By a reduction to Post's Correspondence Problem we provide a direct proof of the known fact that the inclusion problem for unambiguous context-free grammars is undecidable. The argument or some straightforward modiΓΏcation also applies to some other subclasses of context-free languages such as linear

Context-free languages and random walks
Context-free languages and random walks on groups
✍ Wolfgang Woess πŸ“‚ Article πŸ“… 1987 πŸ› Elsevier Science 🌐 English βš– 435 KB

The Green function of an arbitrary, finitely supported random walk on a discrete group with context-free word problem is algebraic. It is shown how this theorem can be deduced from basic results of formal language theory. Context-free groups are precisely the finite extensions of free groups.