## Ambiguity in rewrite systems |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

The Turing Degree of the Inherent Ambiguity | 4 |

Ambiguity in Developmental Systems | 32 |

Systems with Several Letters | 73 |

4 other sections not shown

### Common terms and phrases

ambiguity problem arbitrary contains at least contains no m's context-free grammars COROLLARY counter machine cycle-free derivations DEFINITION degree of unsolvability denote the set derivation in G derivation tree derive a contradiction deterministic context-free languages developmental systems distinct derivations distinguished positions mw^mw^+^m effective family enumerating equivalence classes exist family of languages finite control finite set fixed derivation fully reduced G has production G has surface G is fully Greibach input integer intercalation decomposition Intercalation Theorem label least two elements Lemma length Let G mod G n,m)-bounded natural number node non-empty non-negative integers nonterminal odd loops OL-languages OL-system G pairwise non-equivalent mod parse tree partial algorithm Post correspondence problem production ambiguity proof of Theorem propagating system recursively unsolvable remains to show rewrite systems satisfy conditions sentential forms simulate string subcomputation surface ambiguity symmetric tape symbols terminal symbols Theorem 3.5 Turing degree Turing machine unambiguous word in L(G