On permutation languages

Abstract

In this thesis we investigate some interesting properties of the family of permutation languages and its subclasses. Permutation grammars are context-free grammars extended with special non-context-free rules: permutation rules. Permutation rules have a sequence of nonterminal symbols on the left-hand side and a permutation of that sequence on the right-hand side. The simplest permutation rules are of the form AB -> BA, more complex permutation rules can be obtained by length increase, for instance ABC -> CAB. We discuss some of the subclasses of permutation grammars. We also introduce a modification to Earley's parser algorithm for context-free grammars in order to handle Perm(2, 1) grammars and discuss an efficient implementation.