Accession Number:

ADA009117

Title:

Linear Representation of Tree Structure: A Mathematical Theory of Parenthesis-Free Notations.

Descriptive Note:

Doctoral thesis,

Corporate Author:

STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1974-07-01

Pagination or Media Count:

254.0

Abstract:

Polish notation was discovered by Jan Lukasiewicz in 1924, and has been well known to the computing community since 1954. About 1960 Professor Z. Pawlak, of the Polish Academy of Sciences, discovered another parenthesis-free notation level notation, which superficially resembles Polish notation, but has a markedly different internal structure. A. J. Blikle, a student of Pawlaks, then investigated parenthesis-free notations from a general point of view, and about 1965 discovered an infinite family of parenthesis-free notations the universal orders which includes both Polish notation and level notation. In this dissertation the author develops from first principles a mathematical theory of parenthesis-free notations embracing all of these known notations and many others. To begin, an abstract definition is formulated of parenthesis-free notation, as a mapping of finite plane trees into strings, the circumstances are investigated in which such notations are one-to-one i.e., unambiguous.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE