Necessary conditions for subclasses of random context languages
type: Item
instance of: scholarly article
title: Necessary conditions for subclasses of random context languages
zbMATH Open document ID: 1277.68103
author: Sigrid Ewert
author: Andries van der Walt
published in: Theoretical Computer Science
publication date: 2013-03-04T00:00:00Z
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6140801
zbMATH Keywords: formal language
zbMATH Keywords: regulated rewriting
zbMATH Keywords: random context language
zbMATH Keywords: random forbidding context language
zbMATH Keywords: random permitting context language
zbMATH Keywords: context-free language
zbMATH Keywords: necessary condition
MaRDI profile type: Publication
full work available at URL: j.tcs.2012.12.038
OpenAlex ID: W2015945475
DOI: 10.1016/J.TCS.2012.12.038
Recommended article: A shrinking lemma for random forbidding context languages
Recommended article: Random languages for nonuniform complexity classes
Recommended article: A pumping lemma for random permitting context languages
Recommended article: Q4304532
Recommended article: Some subclasses of context-free languages in \(NC^ 1\)
Recommended article: On Languages Reducible to Algorithmically Random Languages
Recommended article: On complexity classes and algorithmically random languages
Recommended article: A hierarchy of random-context grammars and automata
Recommended article: Nonuniform complexity and the randomness of certain complete languages
Recommended article: Q5507060
description: scientific article; zbMATH DE number 6140801