Volume 31 Issue 1
Jan.  2022
Turn off MathJax
Article Contents
LIU Jin, DUAN Zhenhua, TIAN Cong. Multi-Matching Nested Languages[J]. Chinese Journal of Electronics, 2022, 31(1): 137-145. doi: 10.1049/cje.2020.00.228
Citation: LIU Jin, DUAN Zhenhua, TIAN Cong. Multi-Matching Nested Languages[J]. Chinese Journal of Electronics, 2022, 31(1): 137-145. doi: 10.1049/cje.2020.00.228

Multi-Matching Nested Languages

doi: 10.1049/cje.2020.00.228
Funds:  This work was supported by the National Natural Science Foundation of China (61732013, 61751207), the National Key Research and Development Program of China (2018AAA0103202), and Shaanxi Key Science and Technology Innovation Team Project (2019TD-001)
More Information
  • Author Bio:

    was born in 1991. She received the B.E. degree in computer science and technology from Xidian University, Xi’an, China. She is a Ph.D. candidate of Xidian University. Her research interests include formal methods and program verification. (Email: liujin_xd@163.com)

    (corresponding author) was born in 1948. He received the Ph.D. degree in computer science from the University of Newcastle upon Tyne, U.K., in 1996. He is now a Professor of Xidian University, Fellow of China Computer Federation. His research interests include model checking, network computing, the theory and technology of high-confidence software. (Email: zhhduan@mail.xidian.edu.cn)

    was born in 1981. She received the Ph.D. degree in electronic engineering from Xidian University. She is now a Professor in Xidian University, Distinguished Member of China Computer Federation. Her research interests include formal methods, temporal logic and model checking. (Email: ctian@mail.xidian.edu.cn)

  • Received Date: 2020-08-03
  • Accepted Date: 2020-09-16
  • Available Online: 2021-09-16
  • Publish Date: 2022-01-05
  • 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.
  • loading
  • [1]
    D. Hunter, J. Rafter, and J. Fawcett, Beginning XML, New York: John Wiley & Sons, pp.18–31, 2007.
    V. Kumar, P. Madhusudan, and M. Viswanathan, “Visibly pushdown automata for streaming XML,” in Proc. of the 16th International Conference on World Wide Web, Banff, Alberta, pp.1053–1062, 2007.
    R. Alur and P. Madhusudan, “Adding nesting structure to words,” Journal of the ACM, vol.56, no.3, pp.1–43, 2009.
    R. Alur and P. Madhusudan, “Visibly pushdown languages,” in Proc. of the Thirty-sixth Annual ACM Symposium on Theory of Computing, Chicago, Illinois, pp.202–211, 2004.
    K. G. Hao, Z. H. Duan, and X. Li, “On traceable automata,” Chinese Journal of Computers, vol.5, pp.340–348, 1990. (in Chinese)
    K. G. Hao and Z. H. Duan, “The relationship between DTA and DMTA,” Microelectronics & Computer, vol.4, pp.6–10, 1990. (in Chinese)
    K. G. Hao and Z. H. Duan, “Two fundamental theorems on traceable automata,” Journal of Northwest University (Natural Science Edition), vol.20, no.1, pp.11–17, 1990. (in Chinese)
    R. McNaughton, “Parenthesis grammars,” Journal of the ACM, vol.14, no.3, pp.490–500, 1967. doi: 10.1145/321406.321411
    D. E. Knuth, “A characterization of parenthesis languages,” Information and Control, vol.11, no.3, pp.269–289, 1967. doi: 10.1016/S0019-9958(67)90564-5
    S. Ginsburg and M. A. Harrison, “Bracketed context-free languages,” Journal of Computer and System Sciences, vol.1, no.1, pp.1–23, 1967. doi: 10.1016/S0022-0000(67)80003-5
    E. S. Santos, “A note on bracketed grammars,” Journal of the ACM, vol.19, no.2, pp.222–224, 1972. doi: 10.1145/321694.321696
    J. Berstel and L. Boasson, Formal and Natural Computing, Berlin: Springer, pp.3–25, 2002.
    A. Brüggemann-Klein and D. Wood, “Balanced contextfree grammars, hedge grammars and pushdown caterpillar automata,” in Proc. of Extreme Markup Languages®, Montréal, Quebec, pp.1–16, 2004.
    A. Brüggemann-Klein, M. Murata, and D. Wood, “Regular tree and regular hedge languages over unranked alphabets,” HKUST Theoretical Computer Science Center Research Report, HKUST-TCSC-2001-05, 2001.
    J. Berstel and L. Boasson, “XML grammars”, in Proc. of International Symposium on Mathematical Foundations of Computer Science, Bratislava, pp.182–191, 2000.
    J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, New York: Pearson Education, pp.171–314, 2000.
    K. R. Fall and W. R. Stevens, TCP/IP Illustrated, Volume 1: The Protocols, Hoboken: Addison-Wesley Professional, pp.595–605, 2011.
    M. Bogdanoski, T. Suminoski, and A. Risteski, “Analysis of the SYN flood DoS attack,” International Journal of Computer Network and Information Security, vol.5, no.8, pp.1–11, 2013.
    V. Zlomislić, K. Fertalj, and V. Sruk, “Denial of service attacks: An overview,” in Proc. of 2014 9th Iberian Conference on Information Systems and Technologies, Barcelona, pp.1–6, 2014.
  • 加载中


    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索


    Article Metrics

    Article views (241) PDF downloads(14) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint