Regular cost functions over finite trees

被引:22
作者
Colcombet, Thomas [1 ]
Loeding, Christof [2 ]
机构
[1] Univ Paris Diderot, CNRS, LIAFA, Paris, France
[2] Rhein Westfal TH Aachen, Informatik 7, Aachen, Germany
来源
25TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2010) | 2010年
关键词
tree automata; games; limitedness problem; monadic-second order logic; DESERT AUTOMATA; LIMITEDNESS; LANGUAGES;
D O I
10.1109/LICS.2010.36
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We develop the theory of regular cost functions over finite trees: a quantitative extension to the notion of regular languages of trees: Cost functions map each input (tree) to a value in omega + 1, and are considered modulo an equivalence relation which forgets about specific values, but preserves boundedness of functions on all subsets of the domain. We introduce nondeterministic and alternating finite tree cost automata for describing cost functions. We show that all these forms of automata are effectively equivalent. We also provide decision procedures for them. Finally, following Buchi's seminal idea, we use cost automata for providing decision procedures for cost monadic logic, a quantitative extension of monadic second order logic.
引用
收藏
页码:70 / 79
页数:10
相关论文
共 29 条
[21]   The limitedness problem on distance automata: Hashiguchi's method revisited [J].
Leung, H ;
Podolskiy, V .
THEORETICAL COMPUTER SCIENCE, 2004, 310 (1-3) :147-158
[22]  
MULLER D, 1985, LECT NOTES COMPUT SC, V192, P100
[24]   FINITE AUTOMATA AND THEIR DECISION PROBLEMS [J].
RABIN, MO ;
SCOTT, D .
IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1959, 3 (02) :114-125
[25]   ON SEMIGROUPS OF MATRICES OVER THE TROPICAL SEMIRING [J].
SIMON, I .
RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 1994, 28 (3-4) :277-294
[26]  
SIMON I, 1978, FOCS, P143
[27]  
Thatcher J. W., 1968, Mathematical Systems Theory, V2, P57, DOI 10.1007/BF01691346
[28]  
Thomas W., 1997, Beyond Words, V3, P389, DOI [DOI 10.1007/978-3-642-59126-67, 10.1007/978-3-642-59126-6\\_7]
[29]   FINITE-VALUED DISTANCE AUTOMATA [J].
WEBER, A .
THEORETICAL COMPUTER SCIENCE, 1994, 134 (01) :225-251