Determinization of transducers over finite and infinite words

被引：19

作者：

Béal, MP ^{[1
]}

Carton, O ^{[1
]}

机构：

[1] Univ Marne Vallee, Inst Gaspard Monge, F-77454 Marne La Vallee 2, France

来源：

THEORETICAL COMPUTER SCIENCE | 2002年 / 289卷 / 01期

关键词：

automata; transducers; infinite words; determinization;

D O I：

10.1016/S0304-3975(01)00271-7

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the determinization of transducers over finite and infinite words. The first part of the paper is devoted to finite words. We recall the characterization of subsequential functions due to Choffrut. We describe here a known algorithm to determinize a transducer. In the case of infinite words, we consider transducers with all their states final. We give an effective characterization of sequential functions over infinite words. We describe an algorithm to determinize transducers over infinite words. This part contains the main novel results of the paper. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：225 / 251

页数：27

共 30 条

[1]

[Anonymous], INTRO SYMBOLIC DYNAM

[2]

[Anonymous], 1975, AUTOMATA THEORY FORM

[3]

[Anonymous], HDB THEORETICAL COMP

[4]

Béal MP, 2000, LECT NOTES COMPUT SC, V1853, P561

[5] 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

[6]

BEAL MP, 2000, 200008 I GASP MONG

[7]

BEAL MP, 1993, CODAGE SYMBOLIQUE

[8]

BERSTEL J, 1999, IN PRESS ALGEBRAIC C

[9]

Berstel J., 1979, TEUBNER STUDIENBUCHE, V38

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

BLATTNER, M ;

HEAD, T .

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

← 1 2 3 →