Selectors: a theory of formal languages, semimodular lattices, and branching and shelling processes (Q1069309): Difference between revisions

In this paper, we see how the study of certain hereditary formal languages can lead to an understanding of all sorts of stepwise processes, those falling under the broad headings of branching and shelling processes, and also to a representation of a large class of lattices, which carry the natural logic of these processes. Our basic notion is that of a selector, a hereditary language consisting of words formed from a certain alphabet, and possessed of a unit increase property which guarantees the appearance of a dimension function and forces certain associated lattices of (closed) partial alphabets to be semimodular. A remarkable subclass of selectors consists of those which are locally free. They arise from arbitrary hereditary languages, and form the substrate for the general theory of selectors, since every selector is seen to be a quotient of a locally free selector. Locally free selectors are representable as shelling orders of abstract discs, in the same way that finite distributive lattices are represented by shelling orders (or by linear extensions) of partially ordered sets. Furthermore, every set \(\Gamma\) of linear orders on (or permutations of) a finite set can be completed to the set of bases of a locally free selector \({\bar \Gamma}\). The analogue of the theory of (Dushnik-Miller) dimension is thus available for locally free selectors, and thus for locally free semimodular lattices. Selectors appear as ''greedoids with interval property'' in the work of \textit{B. Korte} and \textit{L. Lovasz} [Lect. Notes Comput. Sci. 117, 205-209 (1981; Zbl 0473.68019)] and \textit{A. Björner} [Matroid theory, Proc. Colloq., Szeged/Hung. 1982, Colloq. Math. Soc. János Bolyai 40, 25-60 (1985)]. For related work concerning geometries defined on partially ordered sets of points, see the work of \textit{U. Faigle} [J. Comb. Theory, Ser. B 28, 26-51 (1980; Zbl 0359.05018)]. For related work on locally free selectors, see the work of \textit{R. Jamison-Waldner}, [Lect. Notes Pure Appl. Math. 76, 113-150 (1982; Zbl 0482.52001)].