A Logical Characterization of Weak Determinism as Simultaneous Application

Abstract Weakly deterministic functions are a subregular class of functions which have been claimed to describe the complexity of most attested phonological maps. This paper proposes a characterization of the weak deterministic functions within the formalism of Boolean Monadic Recursive Schemes (BMRS), in terms of a simultaneous application operator over BMRS programs. This paper provides proof that more complex patterns such as Sour Grapes harmony are not weakly deterministic, and shows that the proposed definition can decisively distinguish between weakly deterministic and properly regular maps. The consequence of this work is a logical characterization of the weakly deterministic boundary, and a testable hypothesis about the complexity of natural language phonological maps.