© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
1
Determinisierung /
Sequentialisierung nicht-sequentieller Transduktoren
Karin Haenelt
Transduktoren für die Sprachverarbeitung
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
2
Determinisierung: Definition
Wir nennen einen Algorithmus,der es ermöglicht,einen nicht-sequentiellenTransduktorin einen endlich-subsequentiellen Transduktor zu überführen,Determinisierung (Mohri 1996)
• Ziel– Zusammenfassung aller Startzustände zu einem Startzustand– Zusammenfassung aller ausgehenden Kanten mit demselben
Symbol zu einer einzigen Kante– Eliminierung von Epsilonkanten
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
3
Beispiel 1nicht-sequentiellerTransduktor
endlich-subsequentiellerTransduktor
0 1b
b2 3 4 5
e hr c
a hr c
6 7 8 9i gr n
a hr c
10 11 12 13e nr n
a nr n
0,ε 1,εb
b
r
a hr c
ech
ing
12,ε 13,εen n
n n
3,e7,i
11,e
4,ec8,in
5,ech9,ing
2,ε6,ε
10,ε
ε ε ε
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
4
Beispiel 2nicht-sequentiellerTransduktor
endlich-subsequentiellerTransduktor
0 1b
b2 3 4 5
e hr c
a hr c
6 7 8i gn
a cc
9 10 11 12e nr n
a nr n
0,ε 1,εb
b
r
a hr c
ech
ing
11,ε 12,εen n
n n
3,e6,i
10,e13,a
4,ec7,in
5,ech8,ing
2,ε9,ε
1413u
u
a
a
14,εau
u
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
5
Prinzip
• Kombination der lokal ambigen Pfade zu einem Pfad, der keine Ausgabe erzeugt
• Verzögerung der Ausgabe bis zur Auflösung der Ambiguität• Verzögerte Ausgabe kann mit einer Mehrzeichen-Ausgabe an
einer Kante zusammengefasst werden
0 1b
b2 3 4 5
e hr c
a hr c
6 7 8 9i gr n
a hr c
0,ε 1,εb
b
r
a hr c
ech
ing
3,e7,i
4,ec8,in
5,ech9,ing
2,ε6,ε
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
6
Konstruktion
• ähnlich wie Potenzmengen-Konstruktion zur Determinisierung nicht-deterministischer Automaten
• mit lazy implementation• hier zusätzlich:
– Verzögerung der Ausgabe, falls zu einer Eingabe verschiedene Ausgaben vorkommen
– neue Zustände gebildet aus Mengen von Paaren (stateT1,string)
• stateT1: Zustand in T1
• string: weitergereichte, d.h. verzögerte Ausgabe
4,ec8,in
{(4,ec),(8,in)}
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
7
Nicht-sequentieller Transduktor ),*,,,,,( 111111 BAFIVT
1V Zustandsmenge
11 VI Menge der Startzustände
11 VF Menge der Endzustände
A Eingabe-Alphabet, endliche Menge von Symbolen B Ausgabe-Alphabet, endliche Menge von Symbolen
1 Zustandsübergangsfunktion 121VAV
1 Ausgabefunktion *11 BVAV
Endlich-Subsequentieller Transduktor ),,*,,,,,( 2222222 BAFiVT
2i einziger Startzustand
2 Zustandsübergangsfunktion 22 VAV
2 Ausgabefunktion *2 BAV
2 Endausgabefunktion *BF
Notationskonventionen, 1
Mohri, 1996
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
8
weitere Notationen yx längstes gemeinsames Präfix zweier Zeichenreihen )(1 xyx
Zeichenreihe y, als Resultat der Abtrennung von x von xy
Q Queue Q zu Verwaltung der Zustandsmengen des resultierenden Transduktors T2
),( wq Element einer Zustandsmenge von T2: q: Zustand aus T1, w: verzögerte Ausgabe
Notationskonventionen, 2
Mohri, 1996
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
9
Notationskonventionen, 3} ),(|),{()( 11 2q(q,w)anddefinedaqwqaJ
)},('),(),(|)',,{()( 1212 aqq and qwq and defined aqqwqaJ
Zustände einer zusammengefassten Zustandsmenge in T2
für die Eingabe a in T1 definiert ist
Abkürzungen
3,e 4c:c
7,i 8c:n
3,ec:c
7,ic:n
Kanten einer zusammengefassten Zustandsmenge in T2
für die Eingabe a mit Zielzustand q‘ in T1 definiert ist
alle Elemente des Repräsentanten {(3,e),(7,i)},in denen gemäß T1 Eingabe c definiert ist
J1(c) = {(3,e),(7,i)}
alle Kanten des Repräsentanten {(3,e),(7,i)},in denen gemäß T1 Eingabe c mit Zielzustand q‘ definiert ist
J2(c) = {(3,e,4),(7,i,8)},
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
10
1 2F 2
1
)},{(2Ii
ii
3 }{ 2iQ 4 while Q 5 do ][2 Qheadq 6 if (there exists 2),( qwq such that 1Fq ) 7 then }{ 222 qFF 8 wq )( 22 9 for each a such that 2),( qwq and ),(1 aq defined
10 do ),( 22 aq )(),( 1 aJwq
)',,(),('
[ 1
1
qaqaqq
w
]
11 ),( 22 aq ))}',,()('),,(
)],([,'{( 1
2
122 qaqw
aJqwqaqq
12 if ( ),( 22 aq is a new state) 13 then ENQUEUE( ),(, 22 aqQ ) 14 DEQUEUE(Q)
*BwhabetAusgabealp BfunktionEndausgabe ktionAusgabefun
tionrgangsfunk ÜbeeEndzuständ F
ndStartzusta
i
)},('),(),(|)',,{()()(),(|),{()(
1212
11
aqq and qwq and defined aqqwqaJ}qwq, and defined aqwqaJ 2
DETERMINIZATION_TRANSDUCER(T1,T2), Mohri 1996
Mohri, 1996Eberhard/Niemann/Sejane, 2004
Algorithmus
xy) von x vonAbtrennungder Resultat (i.e.y Kette )(x -1 xy
y undKetten x der Präfix sgemeinsame längstes yx
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
11
1 2F 2
1
)},{(2Ii
ii
3 }{ 2iQ 4 while Q 5 { ][2 Qheadq 6 if (there exists 2),( qwq such that 1Fq ) 7 { }{ 222 qFF 8 wq )( 22
} 9 for each a such that 2),( qwq and ),(1 aq defined
10 { ),( 22 aq )(),( 1 aJwq
)',,(),('
[ 1
1
qaqaqq
w
]
11 ),( 22 aq ))}',,()('),,(
)],([,'{( 1
2
122 qaqw
aJqwqaqq
12 if ( ),( 22 aq is a new state) 13 then ENQUEUE( ),(, 22 aqQ )
} 14 DEQUEUE(Q)
}
DETERMINIZATION_TRANSDUCER(T1,T2), Mohri 1996
Mohri, 1996
Eberhard/Niemann/Sejane, 2004
Startzustände vereinigen2
Repräsentant für Startzustände in Queue3Schleife über Queue4-14
nächster Repräsentant aus Queue14
Algorithmus: Struktur
Endzustände 7verzögerte Ausgabeals Endausgabe
8
Ausgabe berechnen10
Repräsentant fürZielzustand berechnen
11
Repräsentant fürZielzustand in Queue
12
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
12
9 for each a such that 2),( qwq and ),(1 aq defined 10 do ),( 22 aq
)(),( 1 aJwq)',,(
),('[ 1
1
qaqaqq
w
]
11 ),( 22 aq ))}',,()('),,(
)],([,'{( 1
2
122 qaqw
aJqwqaqq
*BwhabetAusgabealp BfunktionEndausgabe ktionAusgabefun
tionrgangsfunk ÜbeeEndzuständ F
ndStartzusta
i
)},('),(),(|)',,{()()(),(|),{()(
1212
11
aqq and qwq and defined aqqwqaJ}qwq, and defined aqwqaJ 2
xy von x vonAbtrennungder Resultat e. (i. y, Kette )(x
y undKetten x der Präfix sgemeinsame längstes 1- xy
yx
DETERMINIZATION_TRANSDUCER(T1,T2), Mohri 1996
Kern des Determinisierungsalgorithmus
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
13
Zustandsübergänge für {(0,ε)}S (q2)
(q,w)
S
δ1(q1,a) σ2(q2,a) Kommentar
q1 a q1’
(q,w)
J1(a)
[w q1’
δ1(q1,a)
σ1(q1,a,q1’)]
1 2 3 4 5 9 8 7 6 Spalte Erläuterung {(0,ε)} (0,ε) 0 b 1 b 6 Ausgabe einer b-Kante
σ1(0,b,1) b 7 längstes gemeinsames
Präfix der Ausgaben aller b-Kanten σ1(0,b,q1‘)
ε 8 verzögerte Ausgabe (0,ε) εb = b 8-6 Konkatenation Sp. 8 •7 b längstes gemeinsames Präfix aller Zeichenketten
(verzögerte Ausgabe • aktuelle Ausgaben) für alle b-
Kanten, die von allen Paaren (q,w) S ausgehen:
längstes gemeinsames Präfix aller Zeichenketten über die Spalten 8-6
0 1b
b0,εT2 T1
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
14
S (q2)
(q,w)
S
δ1(q1,a) σ2(q2,a) δ2(q2,a)
q1 a q1’ (q,w)
J1(a)
[w q1’
δ1(q1,a)
σ1(q1,a,q1’)]
(q,w,q’)
J2(a)
(q’, [σ2(q2,a)]-1
w σ1(q1,a,q1’))
1 2 3 4 5 9 8 7 6 (0,ε) 0 b 1 b
b ε εb = b (1,b-1b) = (1,ε)
{ (0,ε)}
b {(1,ε)}
Zustandsübergänge für {(0,ε)}
0 1b
b0,εT2 T1
Zustand q‘, verzögerte Ausgabe)
bisher verzögerter Ausgabe w,verkettet mit aktueller Ausgabe
wird links abgeschnitten von
[längste gemeinsame Ausgabe]-1∙angesammelte Gesamtausgabe[σ2(q2,a)]-1 w σ1(q1,a,q1’))
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
15
),(1 aq 2q 2
),(q
wq q a 'q
),( 22 aq ),( 22 aq
)(),( 1 aJwq
[ w
),(' 1 aqq
)',,(1 qaq ] ))',,()],([
,'(
11
22 qaqwaqq
1 2 3 4 5 9 8 7 6 11 10 ),3( e 3 c 4 c (4, ec1][ ) = ),4( ec
e c ec
),7( i 7 c 8 n (8, in1][ ) = ),8( in i n in
{ ),3( e , ),7( i , ),11( e }
= = { ),8(),,4( inec }
Transitionen für {(3,e),(7,i),(11,e)}, c
4 5hchc
8 9gnhc
12 13nnnn
0,ε 1,εb
b
r
ar
3,e7,i
11,e
2,ε6,ε
10,ε
3
7
11
T2 T1
c
4,ec8,in
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
16
Beispiel 1
nicht-sequentiellerTransduktor
p-subsequentiellerTransduktor
0 1b
b2 3 4 5
e hr c
a hr c
6 7 8 9i gr n
a hr c
10 11 12 13e nr n
a nr n
0,ε 1,εb
b
r
a hr c
ech
ing
12,ε 13,εen n
n n
3,e7,i
11,e
4,ec8,in
5,ech9,ing
2,ε6,ε
10,ε
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
17
6 Paar ),3( e Ausgabe )4,,3(1 c 7 Paar ),3( e längstes gemeinsames Präfix aller Ausgaben )',,3(1 qc 8 Paar ),3( e verzögerte Ausgabe w, verkettet mit Spalte 7 9 alle Paare ),3( e , ),7( i längstes gemeinsames Präfix aller Zeichenreihen in Spalte 8
σ2(q2,c) für {(3,e),(7,i),(11,e)}),(1 aq 2q
2
),(q
wq q a 'q
),( 22 aq ),( 22 aq
)(),( 1 aJwq
[ w
),(' 1 aqq
)',,(1 qaq ] ))',,()],([
,'(
11
22 qaqwaqq
1 2 3 4 5 9 8 7 6 11 10 ),3( e 3 c 4 c (4, ec1][ ) = ),4( ec
e = c = ec
),7( i 7 c 8 n (8, in1][ ) = ),8( in i = n = in
{ ),3( e , ),7( i , ),11( e }
= = { ),8(),,4( inec }
)(),( 1 aJwq )',,(1 qaqw
),(' 1 aqq
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
18
6 Paar ),3( e Ausgabe )4,,3(1 c 7 Paar ),3( e alle Ausgaben )',,3(1 qc 8 Paar ),3( e Präfix w alle Ausgaben )',,3(1 qc 9 alle Paare ),7)(,3( ie Präfix w alle Ausgaben )',,3(1 qc und )',,7(1 qc
σ2(q2,c) für {(3,e),(7,i),(11,e)}
längstesgemein-samesPräfixvon
)(),( 1 aJwq )',,(1 qaqw
),(' 1 aqq
),(1 aq 2q 2
),(q
wq q a 'q
),( 22 aq ),( 22 aq
)(),( 1 aJwq
[ w
),(' 1 aqq
)',,(1 qaq ] ))',,()],([
,'(
11
22 qaqwaqq
1 2 3 4 5 9 8 7 6 11 10 ),3( e 3 c 4 c (4, ec1][ ) = ),4( ec
e = c = ec
),7( i 7 c 8 n (8, in1][ ) = ),8( in i = n = in
{ ),3( e , ),7( i , ),11( e }
= = { ),8(),,4( inec }
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
19
Erweiterung des Algorithmus für endlich-subsequentielle
Transduktoren• nicht nur eine, sondern endlich viele Endausgaben• Endausgabe muss eine Menge sein
6 for each 2),( qwq such that 1Fq 7 do }{ 222 qFF 8 ),,(_ 22 wqOUTPUTADD
Mohri, 1996
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
20
Komplexität des subsequentiellen Transduktors
• Zeit– allgemeine Form der Komplexitätskurve ist linear– Laufzeit
• hängt nur von der Länge der Eingabezeichenreihe ab• nicht von der Größe des Automaten
– keine Ambiguitäten zu verwalten
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
21
Komplexität des subsequentiellen Transduktors
• Platz– theoretisch können Transduktoren mit mehr als 2Q Zuständen
entstehen(Anzahl der Teilmengen, die aus n Zuständen gebildet werden kann, beträgt 2n, zusätzlich: Kombinationen mit verzögerten Ausgaben)
– kommt in der Praxis der Sprachverarbeitung kaum vor, da• durch Abfolgebeschränkungen der Zeichen zur Modellierung
menschlicher Sprachen (Laute, Buchstaben, Worte, Kategorien)nicht jeder Zustand mit jedem anderen durch eine Kante verbunden werden kann.
• die Anzahl und Länge der Ambiguitäten praktisch begrenzt ist– praktisch sind die entstehenden endlich-subsequentiellen
Transduktoren oft kleiner als die originalen nicht-sequentiellen Transduktoren
– daher lazy implementation sinnvoll (Zustände nur bilden, wenn sie das Ergebnis einer Transition sind, die von einem bereits hinzugefügten Zustand ausgehen)
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
22
Komplexität: Beispiel 1Name DELAPF
Phonetisch V.3
FDELAF Französisch V.7
EDELAF Englisch
IDELAF Italienisch
Anzahl der Zeilen 472.000 672.000 145.000 612.000
Wörterbücher
Größe 9,6 MB 21,2 MB 3,6 MB 20 MB Anzahl der Zustände 46.750 67.000 47.540 64.390 Anzahl der Kanten 130.125 191.300 115.450 194.606 p 4 7 8 8 Ausgabesymbole, Anzahl
13.490 22.790 14.150 21.870
Ausgabealphabet, Platz
85 KB 116 KB 154 KB 109 KB
Größe 2,1 MB 3,6 MB 2 MB 3,5 MB
Transduktoren
Größe minimiert 870 KB 1,3 MB 790 KB 1,3 MB Konstruktion auf HP-Rechner
9’30’’ 20’ 11’35’’ 19’
Konstruktion auf NEXT-Rechner
38’ 1h21’ 30’ 1h35’
Zeit
Nachschlagen auf HP-Rechner
80 w/ms 80 w/ms 80 w/ms 80 w/ms
(Mohri, 1996)
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
23
Komplexität: Beispiel 2Word lattice W1: Which flights leave Detroit and arrive at Saint-Petersburg around nine a.m.?
Word lattice W2: Determinisierung von W1
Word lattice W3: Minimierung von W2
Mohri, 1997
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
24
Ersparnis durch Determinisierung
• Ein gewichteter Transduktor word lattice für die Spracherkennung auf einem 2.000 Wörter Lexikon für den Satz Which flights leave Detroit and arrive at Saint-Petersburg around nine am?
(Mohri, 1997: 32ff. über ARPA ATIS)
Zustände Übergänge Pfade
WL 106 359 83 Mio.
WL determiniert 38 51 18
WL determiniert und minimiert
25 33 18
Folie von:Eberhard/Niemann/Sejane, 2004: 26
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
25
Komplexität: Determinisierungsalgorithmus
• zeitbestimmender Faktor des Algorithmus:Hashing-Methode, mit der festgestellt wird, ob ein erzeugter Repräsentant eines Zustandes neu oder bekannt ist:if ( is a new state)then ENQUEUE(Q, )),( 22 aq ),( 22 aq
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
26
Determinisierbarkeit
• alle azyklischen Transduktoren können determinisiert werden• zyklische Transduktoren können determinisiert werden, wenn
die Zyklen eine Twins-Property haben• für nicht-determinisierbare Transduktoren können
deterministische Bi-Maschinen konstruiert werden
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
27
Twins-Property / Zwillingseigenschaft
• Choffrut, 1977, 1978– allgemeiner Algorithmus– Nachweis der Entscheidbarkeit
• Allauzen/Mohri– Algorithmus auf der Basis der Komposition von
Transduktoren und einer Charakterisierung der Twins-Property über die Kombinatorik von Worten
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
28
Definition Zwei Zustände eines string-to-weight-Transduktors
),,,,,,,( FIQT , nicht unbedingt sequentiell, heißen Zwillinge, wenn gilt:
)',,'(),,(
)),'('),,(),,(}',({,*)(),( 2
qvqqvqvqqvqquIqqvu
Zwillingseigenschaft
Mohri, 1997:310
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
29
• q1 und q2 sind Geschwister,– wenn sie vom Startzustand über dieselbe Zeichenreihe x erreicht
werden können– wenn es am Zustand q1 und q2 einen Zyklus mit Eingabe y gibt
• Zwei Geschwister q1 und q2 sind Zwillinge– wenn die Minimalausgabe einer Schleife mit Eingabe y bei q1 und
q2 identisch ist• ein Tranduktor T hat die Zwillingseigenschaft, wenn alle Geschwister
Zwillinge sind
Zwillingseigenschaft
Allauzen/Mohri, 2003
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
30
Nicht-sequentialisierbare Transduktoren
Allauzen/Mohri 2003
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
31
Nicht-sequentialisierbare Transduktoren
• Beispiel für eine Funktion, für die es keinen sequentiellen Transduktor gibt:
x:a
x:b0
3
1
4
2x:a
x:a
x:b
x:b
)(,}{ wfxw ist gerade |w| falls a w|| sandernfall b w||
• Bedingung für sequentielle Funktion (Theorem von Ginsburg und Rose, 1966):
dass soexistiert, K Integer positives ein g.d.w. ll sequentieist f.**:f Funktion rationale eine f Sei
f(u)w f(ua):K |w|*,w au ,*,
Mohri, 1997:303
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
32
BiMaschinen
• Geeignet zur Aufteilung eines funktionalen aber nicht sequentiellen Transduktors
• Zwei sequentielle Transduktoren, die in Serie angewendet werden– 1. Hälfte der Bi-Maschine verarbeitet Eingabe von
links nach rechts– 2. Hälfte der Bi-Maschine verarbeitet Ausgabe der
1. Hälfte von rechts nach links
Karttunen 2003:353
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
33
BiMaschine: Beispiel
x:a
x:b0
3
1
4
2x:a
x:a
x:b
x:bx:x1
0 1 2x:x1
x:x2
Nicht-sequentiellerTransduktor LRT
1. Hälfte R
1 0
x2:b
2. Hälfte L
x1:b
x2:a
x1:a
Mohri, 1997:304
x:x10 1
x:x11
x:x22
b:x11 0
b:x10
b:x21
R
L
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
34
Vielen Dank
Für das Aufspüren von Fehlern in früheren Versionen und für Verbesserungsvorschläge danke ich
Simone Eberhardt, Arndt Faulhaber, Julian Kunkel, Katja Niemann, Ineta Sejane
Versionen22.05.2007, 17.05.2007, 23.06.2005,07.05.2005,05.05.2005, 15.01.03
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
35
Literatur• Allauzen, Cyril und Mehryar Mohri (2003). Efficient Algorithms for Testing the
Twins Property. In: Journal of Automata, Languages and Combinatorics 8, 2, S. 117-144.
• Choffrut, Christian (1978). Contributions à l’étude de quelques familles remarquables de fonctions rationelles. PhD thesis (thèse de doctorat d’État), Université Paris 7, LITP: Paris.
• Choffrut, Christian (1977). Une charactérisation des fonctions séquentielles et des fonctions sous-séquentielles en tant que relations rationelles. In: Theoretical Computer Science, 5, S. 325-338.
• Eberhard, Simone; Niemann, Katja und Ineta Sejane (2004). Determinisierung von Transduktoren. Seminarrreferat 28.06.2004. http://kontext.fraunhofer.de/haenelt/kurs/Referate/Eberhard_Niemann_Sejane_S2004/AlgorithmusMohri.ppt bzw. pdf
• Haenelt, Karin (2004). Determinisierung von Transducern. Eine Erläuterung des Algorithmus von Mohri. http://kontext.fraunhofer.de/haenelt/kurs/folien/FstDetermMohri.pdf
• Haenelt, Karin (2004). Operationen auf endlichen Automaten und Transduktoren. Definitionen, Algorithmen, Erläuterungen und Beispiele – eine Übersicht. http://kontext.fraunhofer.de/haenelt/kurs/folien/FSOperationenDef.pdf
© Karin Haenelt, Determinisierung von Transduktoren, 22.05.07/115.01.03
36
Literatur• Karttunen, Lauri (2003): Finite-State Technology. In: Ruslan Mitkov (Hg.): The
Oxford Handbook of Computational Linguistics. Oxford University Press.• Mohri, Mehryar (1997): Finite State Transducers in Language and Speech
Processing. In: Computational Linguistics, 23, 2, 1997, S. 269-311. http://citeseer.nj.nec.com/mohri97finitestate.html
• Mohri, Mehryar (1996): On some Applications of finite-state automata theory to natural language processing. In: Journal of Natural Language Egineering, 2, S. 1-20.
• Mohri, Mehryar und Michael Riley (2002). Weighted Finite-State Transducers in Speech Recognition (Tutorial). Teil 1: http://www.research.att.com/~mohri/postscript/icslp.ps, Teil 2: http://www.research.att.com/~mohri/postscript/icslp-tut2.ps