• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Algebraic informatics >On the Complexity of the Syntax of Tree Languages: Dedicated to Prof. Werner Kuich on the occasion of his retirement
【24h】

On the Complexity of the Syntax of Tree Languages: Dedicated to Prof. Werner Kuich on the occasion of his retirement

机译：关于树语言语法的复杂性：Werner Kuich教授在退休之际献给他

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The syntactic complexity of a tree language is defined according to the number of the distinct syntactic classes of all trees with a fixed yield length. This leads to a syntactic classification of tree languages and it turns out that the class of recognizable tree languages is properly contained in that of languages with bounded complexity. A refined syntactic complexity notion is also presented, appropriate exclusively for the class of recognizable tree languages. A tree language is recognizable if and only if it has finitely many refined syntactic classes. The constructive complexity of a tree automaton is also investigated and we prove that for any reachable tree automaton it is equal with the refined syntactic complexity of its behavior.
机译：树形语言的句法复杂性是根据具有固定屈服长度的所有树的不同句法类别的数量来定义的。这导致对树语言的句法分类，结果表明，可识别树语言的类别正确包含在具有有限复杂性的语言中。还提出了一种完善的句法复杂性概念，该概念仅适用于可识别的树语言类。只有当树语言具有有限的许多精炼语法类时，它才能被识别。还研究了树型自动机的构造复杂性，我们证明对于任何可达的树型自动机，其行为均与精化的语法复杂性相等。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号