处理图像语言的格点自动机与格点文法
作者:
基金项目:

This research is supported by the National Natural Science Foundation of China(国家自然科学基金,No.69673009)


Grid Automata and Grid Grammars for Picture Languages
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [17]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    Giammarresi与Restivo在一篇综述中总结出一个关于可识别的图像语言(即2维矩形语言)REC的等价性定理.对比1维字语言的相应结果,其中还缺少关于生成文法的相应一环.提出了一种(矩形的)格点文法,正好弥补了这一缺环.而取代2维on-line tesselation自动机,引入了格点自动机的概念.一方面,它与经典的2元树型自动机更相似,另一方面,它也是格点文法与等价性定理中关于REC的其他描述方式之间的一座桥梁.同时,标准的existential monadic二阶逻辑也被一种更弱的规范框架——positive monadic分划逻辑所取代.由此导出一个新的更完整的关于REC的等价性定理.

    Abstract:

    A two-dimensional grid grammar was designed to fill up the missing ring in the Equivalence Theorem for recognizable picture languages (REC), summarized in a survey paper by Giammarresi and Restivo. Instead of 2-dimensional on-line tessellation automata, grid automata were introduced, which were closer to the traditional binary tree automata, to bridge the grid grammar and other approaches of describing the class of REC. Meanwhile the standard (existential) monadic second order logic was substituted by a weaker logic framework: positive monadic partition logic. A new and complete version of Equivalence Theorem for REC is presented.

    参考文献
    [1]Inoue K, Nakamura A. A survey of two-dimensional automata theory. LNCS 381, 1990. 72~91
    [2]Thomas W. Elements of an automata theory over partial orders. DIMACS. Series in Discrete Mathematics and Theoretical Computer Science, 1997,29:25~40
    [3]Giammarresi D, Restivo A. Two-Dimensional languages. In: Salomma A, Rozenberg G eds. Handbook of Formal Language. Vol.III, Berlin: Springer-Verlag, 1996. 251~268
    [4]Matz O, Thomas W. The monadic quantifier alternation hierarchy over graphs is infinite. In: Vardi M Y ed. Logics in Computer Science'97, IEEE Symposium. Los Alamitos, California: IEEE Computer Society, 1997. 236~244
    [5]Thomas Wilke. Star-free picture expressions are strictly weaker than first order logic. LNCS 1256, 1997. 347~35
    [6]Siromoney G, Siromoney R, Krithivasan K. Picture languages with array rewriting rules. Information and Control, 1973,22:447~470
    [7]Nivat M, Saoudi A, Dare V. Parallel generation of finite images. International Journal of Pattern Recognition and Artificial Intelligence, 1989,3:279~294
    [8]Thomas W. On logics, tilings and automata. LNCS 530, 1991. 441~454
    [9]Seese D. Interpretability and tree automata: a simple way to solve algorithms on graphs closely related to trees. In: Nivat M et al eds. Tree Automata and Languages. Elsevier, 1992. 83~114
    [10]Shen En-shao. Some notes on graph automata, tiling systems and partition logic. Journal of Computer Science and Technology, 1998,63(6):483~489
    [11]Giammarresi D, Restivo A, Seibert S et al. Monadic second order logic over rectangular pictures and recognizability by tiling systems. Information and Computation, 1996,125:32~45
    [12]Shen En-shao, Tian Q. Monadic partition logics and finite automata. Theoretical Computer Science, 1996,166:63~81
    [13]Pothoff A, Seibert S, Thomas W. Nondeterminism vs. determinism on finite automata over direct acyclic graphs. Bulletin of the Belgian Mathematical Society, Simon Stevin 1, 1994. 285~298
    [14]Latteux M, Simplot D. Context-sensitive string languages and recognizable picture languages. Information and Computation, 1997,138:160~169
    [15]Matz O. Regular expressions and context-free grammars for picture languages. In: Proceedings of the STACS'97. LNCS 1200, 1997. 283~294
    [16]Latteux M, Simplot D. Recognizable picture languages and domino tiling. Theoretical Computer Science, 1997,178(1-2):275~283
    [17]Simplot D. A charaterization of recognizable picture languages by tiling by finite sets. Theoretical Computer Science, 1999,218:297~323
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

沈恩绍.处理图像语言的格点自动机与格点文法.软件学报,2000,11(7):871-880

复制
分享
文章指标
  • 点击次数:3699
  • 下载次数: 4880
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:1998-09-17
  • 最后修改日期:1999-06-22
文章二维码
您是第19795585位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号