The Triple-Pair Construction for Weighted ω-Pushdown Automata

被引：2

作者：

Droste, Manfred ^{[1
]}

Esik, Zoltan ^{[2
]}

Kuich, Werner ^{[3
]}

机构：

[1] Univ Leipzig, Inst Informat, Leipzig, Germany

[2] Univ Szeged, Dept Fdn Comp Sci, Szeged, Hungary

[3] Tech Univ Wien, Inst Diskrete Math & Geometrie, Vienna, Austria

来源：

ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE | 2017年 / 252期

基金：

奥地利科学基金会;

关键词：

D O I：

10.4204/EPTCS.252.12

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let S be a complete star-omega semiring and Sigma be an alphabet. For a weighted omega-pushdown automaton P with stateset {1,..., n}, n >= 1, we show that there exists a mixed algebraic system over a complete semiring-semimodule pair ((S << Sigma* >>)(nxn), (S << Sigma(omega) >>(n)) such that the behavior parallel to P parallel to of P is a component of a solution of this system. In case the basic semiring is B or N-infinity we show that there exists a mixed context-free grammar that generates parallel to P parallel to. The construction of the mixed context-free grammar from P is a generalization of the well known triple construction and is called now triple-pair construction for omega-pushdown automata.

引用

页码：101 / 113

页数：13

共 14 条

[1] Bloom S. L., 1993, Iteration Theories, P159, DOI [DOI 10.1007/978-3-642-78034-9, 10.1007/978-3-642-78034-9_7, DOI 10.1007/978-3-642-78034-9_7]
[2] Bucher W., 1984, THEORETISCHE GRUNDLA
[3] THEORY OF OMEGA-LANGUAGES .1. CHARACTERIZATIONS OF OMEGA-CONTEXT-FREE LANGUAGES
COHEN, RS
GOLD, AY
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1977, 15 (02) : 169 - 184
[4] Conway J.H., 1971, Regular Algebra and Finite Machines
[5] Eilenberg S., 1974, PURE APPL MATH A, V59, DOI [10.1016/S0079-8169(08)60875-2, DOI 10.1016/S0079-8169(08)60875-2]
[6] On iteration semiring-semimodule pairs
Esik, Z.
Kuich, W.
[J]. SEMIGROUP FORUM, 2007, 75 (01) : 129 - 159
[7] Esik Z., 2005, Journal of Automata, Languages and Combinatorics, V10, P243
[8] Ésik Z, 2004, LECT NOTES COMPUT SC, V3113, P68
[9] Esik Zoltan, 2007, Journal of Automata, Languages and Combinatorics, V12, P435
[10] Esik Z., Modern automata theory

← 1 2 →