closure properties on languages

This entry lists some common closure properties on the families of languagesPlanetmathPlanetmath corresponding to the Chomsky hierarchy, as well as other related families.

operationMathworldPlanetmath REG DCFL CFL CSL RC RE
union Y N Y Y Y Y
intersectionMathworldPlanetmathPlanetmath Y N N Y Y Y
set differenceMathworldPlanetmath Y N N Y Y N
complementation Y Y N Y Y N
intersection with a regular language Y Y Y Y Y Y
concatenationMathworldPlanetmath Y N Y Y Y Y
Kleene star Y N Y Y Y Y
Kleene plus Y N Y Y Y Y
reversal Y Y Y Y Y Y
λ-free homomorphismMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath Y N Y Y Y Y
homomorphism Y N Y N N Y
inverseMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath homomorphism Y Y Y Y Y Y
λ-free substitution Y N Y Y Y Y
substitution Y N Y N N Y
λ-free GSM mapping Y N Y Y Y Y
GSM mapping Y N Y N N Y
inverse GSM mapping Y Y Y Y Y Y
k limited erasing Y Y Y Y
rational transduction Y N Y N N Y
right quotient with a regular language Y Y Y N Y
left quotient with a regular language Y Y Y N Y

wherethedefinitionsofthecellsinthetoprowarethefollowinglanguagefamilies: abbreviation name REG regular DCFL deterministic context-free CFL context-free CSL context-sensitive RC recursive RE recursively enumerable
.Basedonthetableabove,studiesinclosurepropertieshavebeenexpandedinotherdirections,suchas • closure properties of the above operations on more families of languages, such as linear languages, indexed languages, and mildly context-sensitive languages • given that an arbitrary family of languages is closed under a subset of operations above, what more can one say about the family? what other closure properties can be deduced? This is known as AFL (abstract family of languages) theory. • closure properties of yet more operations on languages, such as commutative closures, shuffle closures, insertion closures, deletion closures, subword extensions, prefix extensions, and suffix extensions. • knowing that a closure property of an operation is not satisfied for a given language family, study the closure of the property on the family. For example, what is the Boolean closure of context-free languages? • knowning the a closure property of an operation is not satisfied for a given language family, study whether it is decidable that taking the operation on language(s) leads to a language in the family. For example, is it decidable that the intersection of two context-free languages is context-free? Furthermore, if the problem is decidable, what is its complexity?  References 1 A.P.Parkes,IntroductiontoLanguages,Machines,andLogic,Springer(2002). 2 A.Salomaa,FormalLanguages,AcademicPress,NewYork(1973). 3 J.E.Hopcroft,J.D.Ullman,FormalLanguagesandTheirRelationtoAutomata,Addison-Wesley,(1969).Titleclosure properties on languagesCanonical nameClosurePropertiesOnLanguagesDate of creation2013-03-22 18:59:36Last modified on2013-03-22 18:59:36OwnerCWoo (3771)Last modified byCWoo (3771)Numerical id6AuthorCWoo (3771)Entry typeFeatureClassificationmsc 68Q15Classificationmsc 03D55Related topicAbstractFamilyOfLanguages