Lexicographic Decomposition of k-Valued Transducers

被引：13

作者：

Sakarovitch, Jacques ^{[2
]}

de Souza, Rodrigo ^{[1
]}

机构：

[1] Univ Fed Rural Pernambuco, DEINFO, BR-52171900 Recife, PE, Brazil

[2] ENST CNRS, LTCI, Paris, France

来源：

THEORY OF COMPUTING SYSTEMS | 2010年 / 47卷 / 03期

关键词：

Rational relation; k-valued transducer; Unambiguous transducer; Covering of automata; RATIONAL EQUIVALENCE-RELATIONS; FINITE AUTOMATA; DECIDABILITY;

D O I：

10.1007/s00224-009-9206-6

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We give a new, and hopefully more easily understandable, structural proof of the decomposition of a k-valued transducer into k unambiguous functional ones, a result established by A. Weber in 1996. Our construction is based on a lexicographic ordering of computations of automata and on two coverings that can be build by means of this ordering. The complexity of the construction, measured as the number of states of the transducers involved in the decomposition, improves the original one by one exponential.

引用

页码：758 / 785

页数：28

共 25 条

[1]

[Anonymous], 1984, SERIES RATIONNELLES

[2]

[Anonymous], 1975, AUTOMATA THEORY FORM

[3]

[Anonymous], 1979, Transductions and context-free languages

[4]

Béal MP, 2006, LECT NOTES COMPUT SC, V3967, P58

[5]

Béal MP, 2005, LECT NOTES COMPUT SC, V3580, P397

[6] Squaring transducers:: an efficient procedure for deciding functionality and sequentiality [J].

Béal, MP ;

Carton, O ;

Prieur, C ;

Sakarovitch, J .

THEORETICAL COMPUTER SCIENCE, 2003, 292 (01) :45-63

[7] THE EQUIVALENCE OF FINITE VALUED TRANSDUCERS (ON HDT0L LANGUAGES) IS DECIDABLE [J].

CULIK, K ;

KARHUMAKI, J .

THEORETICAL COMPUTER SCIENCE, 1986, 47 (01) :71-84

[8]

de Souza R, 2008, LECT NOTES COMPUT SC, V5257, P252, DOI 10.1007/978-3-540-85780-8_20

[9]

DESOUZA R, 2008, THESIS TELECOM PARIS

[10]

Eilenberg S., 1974, Pure and Applied Mathematics, V59

← 1 2 3 →