Software product line engineering is a common method for designing complex software systems. Feature modeling is the most common approach to specify product lines. A feature model is a feature diagram (a special tree of features) plus some crosscutting constraints. Feature modeling languages are grouped into basic and cardinality-based models. The common understanding of the semantics of feature models is a Boolean semantics. We discuss a major deficiency of this semantics and fix it by applying, in turn, modal logic, the theory of multisets, and formal language theory. In order to adequately represent the semantics of basic models, we propose a Kripke semantics and show that basic feature modeling needs a modal rather than Boolean logic. We propose two multiset based theories for cardinality-based feature diagrams, called flat and hierarchical semantics. We show that the hierarchical semantics of a given cardinality-based diagram captures all information in the diagram. We also charac- terize sets of multisets, which can provide a hierarchical semantics of some diagrams. We provide three different reduction processes going from a cardinality-based diagram to an appropriate regular expression. As for crosscutting constraints, we propose a formal language interpretation of them. We also characterize some existing analysis operations over feature models in terms of operations on the corresponding languages and discuss the relevant decidability problems. / Thesis / Doctor of Philosophy (PhD)