Data representation and lexical calculi

摘要

Notational systems familiar from the elements of discrete mathematical structures are reviewed, extended, and compared for effectiveness in human and mechanical pragmatics. They include representations of labelled trees, simple- and multi-graphs, such as are applied in discussions of data structures, linguistic expressions, state diagrams and flow charts, and the variety of meta-languages for specifying automata, finite state and context-free languages.The algebraic and other structures implied by these notations are discussed, and their use in calculi providing efficient algorithms are illustrated.Examples include: (1) path-naming notations and the calculus of paths, with applications to addressing systems in trees, finite and infinite, and their homomorphic mapping onto graphs; (2) the extension and use of these notations in computing regular expressions from state-diagrams and parsing ambiguities in context-free languages; (3) the use of the resulting calculi in computing unification conditions and equivalence classes of expressions when the representation languages are extended by “monogenic” and “polygenic” systems of explicit definitions.