文章基本信息

标题：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