TITLE:
A Combinatorial Analysis of Tree-Like Sentences
AUTHORS:
Gilbert Labelle, Louise Laforest
KEYWORDS:
Pólya Theory, Combinatorial Species, Digraphs, Tree-Like Sentences
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.5 No.3,
July
24,
2015
ABSTRACT: A sentence over a finite alphabet A, is a finite
sequence of non-empty words over A.
More generally, we define a graphical sentence over A by attaching a non-empty word over A to each arrow and each loop of a connected directed graph
(digraph, for short). Each word is written according to the direction of its
corresponding arrow or loop. Graphical sentences can be used to encode sets of
sentences in a compact way: the readable sentences of a graphical
sentence being the sentences corresponding to directed paths in the digraph. We
apply combinatorial equations on enriched trees and rooted trees, in the
context of combinatorial species and Pólya theories, to analyze parameters in
classes of tree-like sentences. These are graphical sentences constructed on
tree-like digraphs.