Squaring transducers:: an efficient procedure for deciding functionality and sequentiality

被引：49

作者：

Béal, MP

Carton, O

Prieur, C

Sakarovitch, J

机构：

[1] Ecole Natl Super Telecommun Bretagne, Lab Traitement & Commun Informat, CNRS, F-75634 Paris 13, France

[2] Univ Paris 07, CNRS, LIAFA, Paris, France

[3] Univ Marne La Vallee, Inst Gaspard Monge, Noisy Le Grand, France

来源：

THEORETICAL COMPUTER SCIENCE | 2003年 / 292卷 / 01期

关键词：

finite automata; functional transducer; sequential transducer;

D O I：

10.1016/S0304-3975(01)00214-6

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We describe here a construction on transducers that give a new conceptual proof for two classical decidability results on transducers: it is decidable whether a finite transducer realizes a functional relation, and whether a finite transducer realizes a sequential relation. A better complexity follows then for the two decision procedures.

引用

页码：45 / 63

页数：19

共 15 条

[1]

[Anonymous], 1975, AUTOMATA THEORY FORM

[2] Squaring transducers:: An efficient procedure for deciding functionality and sequentiality of transducers [J].

Béal, MP ;

Carton, O ;

Prieur, C ;

Sakarovitch, J .

LATIN 2000: THEORETICAL INFORMATICS, 2000, 1776 :397-406

[3]

BEAL MP, IN PRESS THEORET COM

[4]

Berstel J., 1979, TEUBNER STUDIENBUCHE, V38

[5]

Berstel J., 1985, Pure Appl. Math., V117

[6] SINGLE-VALUED ALPHA-TRANSDUCERS [J].

BLATTNER, M ;

HEAD, T .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1977, 15 (03) :310-327

[7] A proof of Choffrut's theorem on subsequential functions [J].

Bruyère, V ;

Reutenauer, C .

THEORETICAL COMPUTER SCIENCE, 1999, 215 (1-2) :329-335

[8]

CARTON O, 2001, THEORET COMPUT SCI, V250, P71

[9]

Choffrut C., 1977, Theoretical Computer Science, V5, P325, DOI 10.1016/0304-3975(77)90049-4

[10]

Eilenberg S., 1974, AUTOMATA LANGUAGES M, VA

← 1 2 →