AUTOMATA AND LANGUAGES GENERALIZED TO OMEGA-CONTINUOUS SEMIRINGS

被引：15

作者：

KUICH, W

机构：

[1] Institut für Algebra und Diskrete Mathematik, Abteilung für Theoretische Informatik, Technische Universität Wien, A-1040 Wien

来源：

THEORETICAL COMPUTER SCIENCE | 1991年 / 79卷 / 01期

关键词：

Mathematical Techniques;

D O I：

10.1016/0304-3975(91)90147-T

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We generalize the following two language- and automata-theoretic results to omega-continuous semirings. (i) The family of languages accepted by finite automata is the smallest class containing all finite languages and closed under union, product and star (Kleene's Theorem). (ii) The family of languages accepted by pushdown automata is the family of context-free languages.

引用

页码：137 / 150

页数：14