Linear Representation of Tree Structure: A Mathematical Theory of Parenthesis-Free Notations.
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 Pawlak's, 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).
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1974
- Accession Number
- ADA009117
Entities
People
- W. J. Meyers
Organizations
- Stanford University