Member # 1
posted 30. September 2002 08:24
Some Theoretical and Practical Results in Context-Sensitive and Adaptive Parsing
by Quinn Tyler Jackson
ABSTRACT—We introduce a fifth language accepting machine called the PDA-T, demonstrate some of its interesting formal properties, and show its role in the §-Calculus1. Based upon this new machine and the §-Calculus’ other properties, we demonstrate the §-Calculus’ formal Turing Power, and then propose a formal language classification (the §-Hierarchy), derived largely from the Chomsky Hierarchy, but with a fifth class of language accepted by the PDA-T. We show that this modified hierarchy yields several conceptual benefits over the standard four machine Chomsky Hierarchy. We also provide some practical examples of the use of §-grammars in contextsensitive and semantic parsing.
To read the entire paper, please click here
[ 30. September 2002, 08:29: Message edited by: Moderator ]