MINIMIZATION OF RATIONAL WORD FUNCTIONS

被引：19

作者：

REUTENAUER, C ^{[1
]}

SCHUTZENBERGER, MP ^{[1
]}

机构：

[1] ACAD SCI PARIS,F-75016 PARIS,FRANCE

来源：

SIAM JOURNAL ON COMPUTING | 1991年 / 20卷 / 04期

关键词：

RATIONAL FUNCTION; SEQUENTIAL BIMACHINE;

D O I：

10.1137/0220042

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Rational functions from a free monoid into another are characterized by the finiteness of the index of some congruence naturally associated with the function. A sequential bimachine is constructed computing the function, which is completely canonical, and in some sense minimal. This generalizes the Nerode criterion and the minimal automaton of a rational language, and similar results for sequential functions.

引用

页码：669 / 685

页数：17

共 13 条

[1]

Berstel J., 1979, TRANSDUCTIONS CONTEX

[2]

BERSTEL J, 1985, THEORY CODES

[3]

BOE JM, 1979, THEORIE CODES, P9

[4] COUNTING WITH RATIONAL FUNCTIONS [J].

CHOFFRUT, C ;

SCHUTZENBERGER, MP .

THEORETICAL COMPUTER SCIENCE, 1988, 58 (1-3) :81-101

[5] PROPERTIES OF FINITE AND PUSHDOWN TRANSDUCERS [J].

CHOFFRUT, C ;

CULIK, K .

SIAM JOURNAL ON COMPUTING, 1983, 12 (02) :300-315

[6]

Eilenberg S., 1974, AUTOMATA LANGUAGES M, VA

[7]

Ginsburg S., 1962, INTRO MATH MACHINE T

[8]

Lothaire M., 1983, COMBINATORICS WORDS

[9]

Pin J.-E., 1984, VARIETES LANGAGES FO

[10]

REUTENAUER C, IN PRESS LECTURE NOT

← 1 2 →