Multidimensional trees (Q1178697)

This paper considers a generalization of both techniques for defining formal languages: the generative schemes, for example grammars and automata, which decide whether a particular string belongs to a language. A new data structure is presented, called a multidimensional tree. It is an extension of the normal concept of a tree, which is a two-dimensional concept, into higher dimensions. A formal definition of the concept of multidimensional forests over an alphabet \(\Sigma\), of dimension \(n\) and degree \(k\), denoted \(T^ k_ n(\Sigma)\) is given. If \(V\) is a ranked set, \(T^ k_ n(\Sigma,V)\) is a multidimensional forest with variables \(V\), and is defined as the smallest set such that some properties are fulfilled. The grammars \(G^ k_ n\) are defined like a four-tuple \(G=(\Sigma,V,P,S)\), where \(P\) is a ranked set of productions and \(S\) is a start symbol. The language is associated with \(G^ k_ n\) as usually. A nondeterministic finite automaton \(A^ k\) is defined such that the set of languages recognizable by this automaton is the same as the set of languages generable from grammars. The authors remark that this work has many possible extensions and that \(G^ k_ n\) grammars may offer a reasonable alternative to context free grammars for specifying languages.