Two notions of strong equivalence

In this talk, I propose two notions of equivalence between grammars and grammar formalisms that are useful for comparing not only which strings can be generated, but also how they are generated. If a sentence is ambiguous in a language, a suitable grammar should derive that sentence in multiple ways. In the first notion, two grammars are equivalent if they generate each string in the same number of ways. The second involves considering all possible homomorphic functions over derivation trees, including the usual semantic interpretations. Taking this perspective, two grammars are equivalent if they generate the same sets of string-interpretation pairs. I will demonstrate how these two notions apply to Context-Free Grammars and Pushdown Automata, as well as to Head Grammars and Linear Indexed Grammars, and discuss how studying translations between equivalent grammar formalisms sheds light on the recursive mechanisms underlying each formalism.

Location: Fowler Museum A139