Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement

Details Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement

2009-07-29

arxiv.org/abs/0907.5132v1

EPTCS 3, 2009, pp. 183-192

Computer Science

Formal Languages and Automata Theory

Scientific paper

10.4204/EPTCS.3.17

Recently, it has been shown that every recursively enumerable language can be generated by a scattered context grammar with no more than three nonterminals. However, in that construction, the maximal number of nonterminals simultaneously rewritten during a derivation step depends on many factors, such as the cardinality of the alphabet of the generated language and the structure of the generated language itself. This paper improves the result by showing that the maximal number of nonterminals simultaneously rewritten during any derivation step can be limited by a small constant regardless of other factors.

Affiliated with

Also associated with

No associations

Rating

Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-521692