This paper provides a new formalization for the class of binary multinomial processing tree (BMPT) models, and new theorems for the class are developed using the formalism. MPT models are a popular class of information processing models for categorical data in specific cognitive paradigms. They have a recursive structure that is productively described with the tools of formal language and computation theory. We provide a proof-theoretic axiomatization that characterizes BMPT models as strings in a context free language, and then we add model- theoretic axioms to interpret the strings as parameterized probabilistic models for categorical data. The language for BMPT models is related to the Dyck language, a well-studied context free language. Once BMPT models are viewed from the perspective of the Dyck language, a number of theoretical and computational results can be developed. We first look at the sub-class of BMPT models that satisfy a uniqueness condition, namely that they have unique categories and parameters. First, we give a complete enumeration of the models under the uniqueness condition. Second, we show when two such models are statistically equivalent. Third, we use the pushdown automaton associated with the Dyck language to partition the models and develop algorithms that compute the probability distribution functions (pdfs) for any given model. Lastly, we relax the uniqueness assumption and we modify the aforementioned algorithms to generate the pdfs for models under linear-order parameter constraints. |