Knowledge and Expectation Formulae for Parsing
by
Paola Glavan
University of Zagreb, FSB

The mechanism of knowledge and expectation formulae can provide adequate syntactic analysis of German text, with smooth extension to at least elements of semantic analysis. It can be efficiently implemented, in the form of a running parser-generator, and integrated with the lexical analyzer being developed. It can be completely formally specified using distributed Abstract State Machines (ASM), and the correctness of the implementation with respect to formal specification can be proved.

As the dynamics of knowledge and expectation formulae is inherently distributed, it suggests connections to other formalisms, such as the Chemical Abstract Machine (CHAM) and versions of Linear Logic . Also, existence of the symmetries between expectation formulae suggests opimizations for parsing strategies.

By investigating the symmetries of expectations and the structure of the dynamics of verifying knowledge and expectation formulae for concrete nontrivial fragments of German grammar, we expect to achieve at least these two goals:

• Derive complexity estimates and efficient strategies for both sequential and distributed parsers, verifying the optimizations introduced by purely logical means;
• Relying on such structures, investigate the relations to formalisms such as CHAM, version of Linear Logic, Lambek calculus, leading to their eventual novel applications.

Date received: March 15, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caex-29.