The Mobius function of generalized factor order

We use discrete Morse theory to determine the Mobius function of generalized factor order. Ordinary factor order on the Kleene closure A* of a set A is the partial order defined by letting u <= w if w contains u as a subsequence of consecutive letters. Generalized factor order takes into account a partial order P-A on the alphabet A, that is, u <= w whenever w contains a subsequence w(i + 1) . . . w(i + vertical bar u vertical bar) such that for each j, u(j) <= w(i + j) in A. Using Babson and Hersh's application of Robin Forman's discrete Morse theory to poset order complexes, we are able to give a recursive formula for the Mobius function in the case where each element of A covers a unique letter in P-A. (C) 2012 Elsevier B.V. All rights reserved.