Efficient generation of combinatorial objects is a well-researched area. Among them many literature devoted on the combinatorial Gray code approach where the goal is to find a Hamiltonian path or cycle in a representative graph of the corresponding combinatorial class. Another approach namely genealogical tree approach has been recently introduced where the goal is to find a rooted spanning tree in the representative graph. Researchers have also focused on finding general patterns in the generation techniques of combinatorial classes so that common approaches can be applied to a large number of related problems. Here, we propose a unifying framework for combinatorial generation by giving recursive definition of an abstract combinatorial class. The definition can be instantiated to an array of specific combinatorial classes namely n-tuple, combination, integer partition, set partition and binary trees by specifying the framework parameters appropriately. As an illustration, we show the instantiation of the combinatorial class of n-tuples, combinations and balanced parenthesis strings and also give novel constant-time generation algorithm for each of them.

Deep linguistic processing is a research-intensive area with several potential applications. Amidst the vast literature on formal linguistic theory, Head- driven Phrase Structure Grammar (HPSG) has a unique position, since it combines the best features of the contemporary approaches as well as establishes an integrated framework for cross-layer representation of linguistic objects. There is very few HPSG analysis of Arabic morphological, syntactic and semantic features. Arabic is the best instance of nonconcatenative morphology among the living languages. Arabic verb system shows a rich morphology, capable of lexically expressing diverse syntactic and semantic phenomena. Formalisms of existing morphological analyzers for Arabic cannot capture this higher layer diversity due to a lack of mathematical rigor and expressiveness. In this book, we discuss the HPSG framework to support rich nonconcatenative morphology of Arabic verbs. We present HPSG analysis of the agency of Arabic passives and reflexives as well as morphologically complex predication of causatives in accordance with the existing analysis in other languages.