A new parallel algorithm for parsing arithmetic infix expressions

A new parallel algorithm for transforming an arithmetic infix expression into a par se tree is presented. The technique is based on a result due to Fischer (1980) which enables the construction of the parse tree, by appropriately scanning the vector of precedence values associated with the elements of the expression. The algorithm presented here is suitable for execution on a shared memory model of an SIMD machine with no read/write conflicts permitted. It uses O(n) processors and has a time complexity of O(log2n) where n is the expression length. Parallel algorithms for generating code for an SIMD machine are also presented.

Woher kommen die Infixe im Isu (Kameruner Grasland)?

Die westliche Ring-Sprache Isu (Süd-Bantoid) des Kameruner Graslands setzt ein palatales Infix zum Ausdruck einer Reihe verwandter verbaler Funktionen – imperfektiver Aspekt, Pluraktional, Kausativ – ein. Damit hebt sie sich deutlich vom engeren Bantu- und weiteren Benue-Kongo-Habitus ab, der sich dadurch auszeichnet, Kategorien dieser Art entweder durch verbale Suffixe oder durch Periphrase mithilfe von Hilfsverben zu kodieren. Morphologische Distributionsanalyse, interne Rekonstruktion und externer Vergleich innerhalb der Ring-Gruppe ermöglichen es, die historischen Ursprünge dieses palatalen Infixes einzukreisen und es als Abbauprodukt einer Hochvokal-Reduplikation (ursprünglich in Progressivfunktion) zu identifizieren, wie sie (a) in anderen Niger-Kongo-Sprachen nicht unüblich ist, und (b) wie sie sogar als kognate Vorläuferkonstruktion in der Süd-Ring-Sprache Babungo nachgewiesen werden kann. Funktional-diachron gesehen, wurde im Isu ein vormaliger Progressiv in zunehmendem Maße als Imperfektiv grammatikalisiert und ist damit in die Domäne der älteren Imperfektiv-Strategie -ə (< *-a) eingedrungen. Auf diese Art fügen sich das Isu und seine nächsten Verwandten trotz dieser eigentümlichen Infix-Phänomene sauber in das Gesamtbild westafrikanischer Sprachen ein.