๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Minimization of the complexity function in the class of pushdown store automata and categorial grammars of complexity three

โœ Scribed by A. Ya. Dikovskii; L. S. Modina

Publisher
Springer US
Year
1968
Tongue
English
Weight
586 KB
Volume
7
Category
Article
ISSN
0002-5232

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

On complexity of the word problem in bra
On complexity of the word problem in braid groups and mapping class groups
โœ Hessam Hamidi-Tehrani ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 350 KB

We prove that the word problem in the mapping class group of the once-punctured surface of genus g has complexity O(|w| 2 g) for |w| log(g) where |w| is the length of the word in a (standard) set of generators. The corresponding bound in the case of the closed surface is O(|w| 2 g 2 ). We also carry