Default Finite State Machines And Finite State Phonology

We propose DFSM's as an extension of finite state machines, explore some of their properties, and indicate how they can be used to formalize naturally occurring linguistic systems. We feel that this implementation of two-level rules may be more linguistically natural and easier to work with computationally. We provide complexity results that shed light on the computational situation. INTRODUCTION Two-level phonology combines the computational advantages of finite state technology with a formalism that permits phenomena to be described with familiar-looking rules. The problem with such a scheme is that, in practice, the finite state machines (FSM's) can grow too large to be manageable; one wants to describe them and to run them without having to deal with them directly. The Kimmo approach 1 seeks to achieve this by (1) decomposing the computational process into a battery of parallel finite state machines and (2) compiling rules (which notationally resemble familiar phonological rule..