Multi-Matching Nested Languages

The data with both a linear ordering and a hierarchically nested one-to-one matching of items is ubiquitous, including parenthesis matching languages and hypertext markup language/extensive markup language (HTML/XML) documents. There exist some real-world problems which are beyond one-to-one matching. They have a multi-matching structure including one-to-n or n-to-one matching relation. Multiple threads can simultaneously read the same file, one block of memory can be referenced by multiple pointers in programs. We propose a new model of multi-matching nested relations consisting of a sequence of linearly ordered call, return and internal positions and augmented with one-to-one, one-to-n or n-to-one matching nested edges from calls to returns. Via linear encoding by introducing tagged letters, multi-matching nested words are obtained over a tagged alphabet. We put forward multi-matching nested traceable automata and the accepted languages are called multi-matching nested languages. Multi-matching nested grammars are presented which have the same expressive power as the proposed automata. An application is displayed to illustrate how the automata work.