%latex
\title{A permutation based grammar approach}
\author{Patrick Hammer}
\maketitle
\section{Motivation}
In some cases, for example natural language, it may be easier to forbid several permutations on words by rules, because they would give them a different meaning, or because they would not be in the language anymore (because of grammar for example), than always trying to model the allowed and not allowed cases, again and again for different permutations, to make it more flexible. This paper describes the basic mathematical machinery needed for this approach, and proves that it has the same mightiness like unrestricted grammars.
\section{Permutation set}
A permutation set of a set or a tuple M, let's write $perm(M)$, is the set of all possible permutations of the elements in M. (it contains $|M|!$ elements)
\section{Conditional permutation set}
A conditional permutation set of a set or a tuple M, and a set of logical conditions C, let's write $cperm(M,C)$, is defined as $perm(M)\setminus F$, where F is the "forbidden" set of permutations: $\{x \in perm(M) | x $ satisfies $ c $ $\forall c \in C\}$.
\section{Common definition of a formal language}
A formal language L over an alphabet A is a subset of A*, which is a set of words over A.
\section{Permutation based language}
If the language $L$ is defined as $\bigcup_{i=0}^{\infty}( cperm(B,C) | B$ tuple$\wedge |B|=i \wedge \forall b \in B: b \in A) \Leftrightarrow \{B$ tuple$| \forall b \in B: b \in A \wedge B$ doesn't satisfy $c \forall c \in C \}$ with arbitrary $C$, "grammar" may be represented with $C$. We notice that this definition restricts our language, but how much? While there exist formal languages where no Turing machine could decide if a word is in the language, this does not hold for $L$, because $L$ wouldn't even be defined if any of the elements in $C$ would not be decideable. Therefore, because the elements in $C$ are only limited by this, Permutation based languages are recursively enumerable, which means they are of Type 0 in the Chomsky hierarchy. Unrestricted grammars are in the same category.
