首页    期刊浏览 2024年12月11日 星期三
登录注册

文章基本信息

  • 标题:Minimizing Finite Automata with Graph Programs
  • 本地全文:下载
  • 作者:Detlef Plump ; Robin Suri ; Ambuj Singh
  • 期刊名称:Electronic Communications of the EASST
  • 电子版ISSN:1863-2122
  • 出版年度:2011
  • 卷号:39
  • 语种:English
  • 出版社:European Association of Software Science and Technology (EASST)
  • 摘要:GP (for Graph Programs) is a rule-based, nondeterministic programming language for solving graph problems at a high level of abstraction, freeing programmers from dealing with low-level data structures. In this case study, we present a graph program which minimizes finite automata. The program represents an automaton by its transition diagram, computes the state equivalence relation, and merges equivalent states such that the resulting automaton is minimal and equivalent to the input automaton. We illustrate how the program works by a running example and argue that it correctly implements the minimization algorithm of Hopcroft, Motwani and Ullman. We also prove a quadratic upper bound for the number of rule schema applications used by the program.
国家哲学社会科学文献中心版权所有