Book contents
- Frontmatter
- Contents
- Foreword
- Preface
- Preface to this edition
- Chapter 1 Words
- Chapter 2 Square-Free Words and Idempotent Semigroups
- Chapter 3 Van der Waerden's Theorem
- Chapter 4 Repetitive Mappings and Morphisms
- Chapter 5 Factorizations of Free Monoids
- Chapter 6 Subwords
- Chapter 7 Unavoidable Regularities in Words and Algebras with Polynomial Identities
- Chapter 8 The Critical Factorization Theorem
- Chapter 9 Equations in Words
- Chapter 10 Rearrangements of Words
- Chapter 11 Words and Trees
- Bibliography
- Index
Chapter 11 - Words and Trees
Published online by Cambridge University Press: 04 November 2009
- Frontmatter
- Contents
- Foreword
- Preface
- Preface to this edition
- Chapter 1 Words
- Chapter 2 Square-Free Words and Idempotent Semigroups
- Chapter 3 Van der Waerden's Theorem
- Chapter 4 Repetitive Mappings and Morphisms
- Chapter 5 Factorizations of Free Monoids
- Chapter 6 Subwords
- Chapter 7 Unavoidable Regularities in Words and Algebras with Polynomial Identities
- Chapter 8 The Critical Factorization Theorem
- Chapter 9 Equations in Words
- Chapter 10 Rearrangements of Words
- Chapter 11 Words and Trees
- Bibliography
- Index
Summary
Introduction
The aim of this chapter is to give a detailed presentation of the relation between plane trees and special families of words: parenthesis systems and other families. The relation between trees and parenthesis notation is classical and has been known perhaps since Catalan 1838.
Because trees play a central role in the field of combinatorial algorithms (Knuth 1968), their coding by parenthesis notation has been investigated so very often that it is quite impossible to give a complete list of all the papers dealing with the topic. These subjects are also considered in enumeration theory and are known to combinatorialists (Comtet 1970) as being counted by Catalan numbers. Note that a generalization of the type of parenthesis system often called Dyck language is a central concept in formal language theory. These remarks give a good account of the main role played by trees and their coding in combinatorics on words.
Presented here are three ways to represent trees by words. The first one consists in constructing a set of words (one for each node) associated to a plane tree. The second is the classical parenthesis coding, and the third concerns Lukaciewicz language (known also as Polish notation).
The combinatorial properties of Lukaciewicz language were investigated by Raney (1960) in order to give a purely combinatorial proof of the Lagrange inversion formula (see also Schiitzenberger 1971). This proof is presented in Section 11.4 of the present chapter as an application of our combinatorial constructions.
- Type
- Chapter
- Information
- Combinatorics on Words , pp. 213 - 227Publisher: Cambridge University PressPrint publication year: 1997