Multidimensional trees
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.
- scientific article; zbMATH DE number 2127736
- Multidimensional bipartite trees
- Higher Dimensional Trees, Algebraically
- Multidimensional balanced binary trees
- On the dimension of trees
- Hypertrees
- Tree embeddings
- scientific article; zbMATH DE number 168426
- Tree self-embeddings
- scientific article; zbMATH DE number 19200
- A generalized approach to formal languages
- Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Indexed Grammars—An Extension of Context-Free Grammars
- Mappings and grammars on trees
- Nested Stack Automata
- The IO- and OI-hierarchies
- Rooted tree maps
- Multidimensional trees and a Chomsky-Schützenberger-Weir representation theorem for simple context-free tree grammars
- Higher Dimensional Trees, Algebraically
- The Multiattribute Utility Tree
- Directed rooted forests in higher dimension
- On the dimension of trees
- A refined enumeration of hex trees and related polynomials
- The bi-dimensional directed IDLA forest
This page was built for publication: Multidimensional trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1178697)
