文章基本信息
- 标题：Unambiguous Separators for Tropical Tree Automata
- 本地全文：下载
- 作者：Thomas Colcombet ; Sylvain Lombardy
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：154
- 页码：32:1-32:13
- DOI：10.4230/LIPIcs.STACS.2020.32
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：In this paper we show that given a max-plus automaton (over trees, and with real weights) computing a function f and a min-plus automaton (similar) computing a function g such that f ⩽ g, there exists effectively an unambiguous tropical automaton computing h such that f ⩽ h ⩽ g. This generalizes a result of Lombardy and Mairesse of 2006 stating that series which are both max-plus and min-plus rational are unambiguous. This generalization goes in two directions: trees are considered instead of words, and separation is established instead of characterization (separation implies characterization). The techniques in the two proofs are very different.
- 关键词：Tree automata; Tropical semiring; Separation; Unambiguity
