The complexity of the membership problem for some extensions of context-free languagest†

†This work is supported in part by NSF Grant No. GJ-43228. Some of these results have appeared in conference proceedings, see [41] and [42].

Abstract

The time and tape complexity of some families of languages defined in the literature by altering methods of generation by context-free grammars is considered. Specifically; it is shown that the following families of languages can be recognized by deterministic multitape Turing machines either in polynomial time or within (log n)² tape:

1) the context independent developmental (EOL) languages;

2) the simple matrix languages;

3) the languages generated by derivation restricted state grammars.:

4) the languages generated by linear context-free grammars with certain non-regular control sets;

5) the languages generated by certain classes of vector grammars.

In fact, these languages are of the same tape complexity as context-free languages. Other results indicate the complexity of EDOL languages and the effects on complexity of applying the homomorphic replication operator to regular and context-free languages.

Keywords:

• time complexity
• tape complexity
• developmental languages
• matrix grammars
• vector grammars
• state grammars
• linear grammars
• control sets
• context-free languages
• log-tape reducibility
• homomorphic replication operator

C.R. Categories:

• 5.23
• 5.25

†This work is supported in part by NSF Grant No. GJ-43228. Some of these results have appeared in conference proceedings, see [41] and [42].

†This work is supported in part by NSF Grant No. GJ-43228. Some of these results have appeared in conference proceedings, see [41] and [42].

Notes

†This work is supported in part by NSF Grant No. GJ-43228. Some of these results have appeared in conference proceedings, see [41] and [42].