Multi-Matching Nested Languages
Multi-Matching Nested Languages作者机构：ICTT and ISN Laboratory Xidian University
出 版 物：《Chinese Journal of Electronics》 (电子学报(英文))
年 卷 期：2022年第31卷第1期
页 面：137-145页
核心收录：
学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）]
基 金：supported by the National Natural Science Foundation of China (61732013, 61751207) the National Key Research and Development Program of China (2018AAA0103202) Shaanxi Key Science and Technology Innovation Team Project (2019TD-001)
主 题：multimatching nested traceable automata hypermedia markup languages multimatching nested relations multimatching nested languages multimatching structure computational complexity multimatching nested words grammars linear ordering parenthesis matching languages multiple pointers matching nested edges internal positions accepted languages multiple threads multimatching nested grammars XML matching relation via linear encoding
摘 要：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 nto-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 nto-one matching nested edges from calls to returns. Via linear encoding by introducing tagged letters, multimatching nested words are obtained over a tagged alphabet. We put forward multi-matching nested traceable automata and the accepted languages are called multimatching 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.
同方期刊数据库