首页    期刊浏览 2025年07月27日 星期日
登录注册

文章基本信息

  • 标题:On Unambiguous Regular Tree Languages of Index (0,2)
  • 本地全文:下载
  • 作者:Jacques Duparc ; Kevin Fournier ; Szczepan Hummel
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2015
  • 卷号:41
  • 页码:534-548
  • DOI:10.4230/LIPIcs.CSL.2015.534
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:Unambiguous automata are usually seen as a natural class of automata in-between deterministic and nondeterministic ones. We show that in case of infinite tree languages, the unambiguous ones are topologically far more complicated than the deterministic ones. We do so by providing operations that generate a family (A_{alpha})_{alpha omega^x: an ordinal tremendously larger than (omega^(omega))^3 +3 which is the height of the Wadge hierarchy of deterministic tree languages as uncovered by Filip Murlak. 3. The priorities of all these parity automata only range from 0 to 2.
  • 关键词:Tree Automata; Unambiguity; Wadge Hierarchy.
国家哲学社会科学文献中心版权所有