Рационалды серия - Википедия - Rational series

Математика мен информатикада а рационалды қатар тұжырымдамасын жалпылау болып табылады ресми қуат сериялары астам сақина негізгі алгебралық құрылым сақина емес, а болған жағдайда семиринг, және анықталмайды іргелес деп болжанбайды жүру. Оларды а-ның алгебралық өрнектері деп санауға болады ресми тіл ақырлы алфавит.

Анықтама

Келіңіздер R болуы а семиринг және A ақырлы алфавит.

A коммутативті емес көпмүшелік аяқталды A сөздердің ақырғы формальды жиынтығы A. Олар семирингті құрайды .

A ресми сериялар Бұл R-қызметі в, үстінде ақысыз моноид A*, ретінде жазылуы мүмкін

Формальды қатарлар жиыны белгіленеді және операциялар шеңберінде семирингке айналады

Коммутативті емес көпмүшелік функцияға сәйкес келеді в қосулы A* ақырғы қолдау.

Бұл жағдайда R сақина, содан кейін бұл Магнус сақинасы аяқталды R.[1]

Егер L аяқталған тіл A, ішкі бөлігі ретінде қарастырылады A* біз қалыптастыра аламыз сипаттамалық қатарлар туралы L ресми серия ретінде

сәйкес келеді сипаттамалық функция туралы L.

Жылы әрекетін анықтауға болады қайталану ретінде көрсетілген

және ретінде ресімделген

The ұтымды операциялар формальды қатарларды итерациямен бірге қосу және көбейту болып табылады рационалды қатар - бастап рационалды амалдар арқылы алынған формальды қатар .

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ Кох, Гельмут (1997). Алгебралық сандар теориясы. Энцикл. Математика. Ғылыми. 62 (1-ші басылымның 2-ші басылымы). Шпрингер-Верлаг. б. 167. ISBN  3-540-63003-1. Zbl  0819.11044.

Әрі қарай оқу

  • Сакарович, Жак (2009). Автоматтар теориясының элементтері. Француз тілінен Рубен Томас аударған. Кембридж: Кембридж университетінің баспасы. IV бөлім (олар осында аталады) - рационалды серия). ISBN  978-0-521-84425-3. Zbl  1188.68177.
  • Дросте, М., & Куйч, В. (2009). Семирингтер және ресми қуат сериялары. Салмақталған автоматтар туралы анықтама, 3–28. дои:10.1007/978-3-642-01492-5_1
  • Сакарович, Дж. Рационалды және танылатын қуат сериясы. Салмақталған автоматтар туралы анықтама, 105–174 (2009). дои:10.1007/978-3-642-01492-5_4
  • В.Куйч. Семирингтер және ресми қуат сериялары: олардың формальды тілдерге және автоматтар теориясына сәйкестігі. Г.Розенберг пен А.Саломаа, редакторлар, Ресми тілдер анықтамалығы, 1 том, 9 тарау, 609–677 беттер. Шпрингер, Берлин, 1997 ж