16ab7cd853e9c15cf986a8a7c3db1f8d20e275409Sebastian Redl// fstlib.h
22cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor
32cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// Licensed under the Apache License, Version 2.0 (the "License");
42cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// you may not use this file except in compliance with the License.
52cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// You may obtain a copy of the License at
62cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor//
72cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor//     http://www.apache.org/licenses/LICENSE-2.0
82cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor//
92cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// Unless required by applicable law or agreed to in writing, software
10c43b54cbc10654ed59de797898042e1a05265246Sebastian Redl// distributed under the License is distributed on an "AS IS" BASIS,
112cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
122cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// See the License for the specific language governing permissions and
138b12273c86ede439edf52d35b170fd32b2ed49d4Sebastian Redl// limitations under the License.
14f29f0a28c4d9599b389bbb6d186e14af753dc5a3Sebastian Redl//
15f29f0a28c4d9599b389bbb6d186e14af753dc5a3Sebastian Redl// Copyright 2005-2010 Google, Inc.
162cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// Author: riley@google.com (Michael Riley)
17f0aaf7a59729a4ae0146e3464ee987745be95829Douglas Gregor//
1830a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// \page FstLib FST - Weighted Finite State Transducers
19833ca991c1bfc967f0995974ca86f66ba1f666b5John McCall// This is a library for constructing, combining, optimizing, and
200a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor// searching "weighted finite-state transducers" (FSTs). Weighted
211afb661bc5444462a246cefa0effa61ef25fab29Jonathan D. Turner// finite-state transducers are automata where each transition has an
221afb661bc5444462a246cefa0effa61ef25fab29Jonathan D. Turner// input label, an output label, and a weight. The more familiar
23668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor// finite-state acceptor is represented as a transducer with each
247f94b0b0c6791013d2f72ced9b4bedd3b23673a6Douglas Gregor// transition's input and output the same.  Finite-state acceptors
25c544ba09695e300f31355af342258bd57619e737Douglas Gregor// are used to represent sets of strings (specifically, "regular" or
2630a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// "rational sets"); finite-state transducers are used to represent
2730a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// binary relations between pairs of strings (specifically, "rational
2830a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// transductions"). The weights can be used to represent the cost of
2930a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// taking a particular transition.
3030a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth//
3130a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// In this library, the transducers are templated on the Arc
3230a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// (transition) definition, which allows changing the label, weight,
3330a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// and state ID sets. Labels and state IDs are restricted to signed
3417fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor// integral types but the weight can be an arbitrary type whose
350a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor// members satisfy certain algebraic ("semiring") properties.
360a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor//
3730a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// For more information, see the FST Library Wiki page:
38ce12d2f8863588d408897602089d17c4d3c3d0e5Douglas Gregor// http://wiki.corp.google.com/twiki/bin/view/Main/FstLibrary
392cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor
400f75323264b93a318ac9007eb5ec5b233c444068Douglas Gregor// \file
410f75323264b93a318ac9007eb5ec5b233c444068Douglas Gregor// This convenience file includes all other FST inl.h files.
422cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor//
43dc3c0d20375bda7775b2fade05b20e315798b9feDaniel Dunbar
442cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#ifndef FST_LIB_FSTLIB_H__
4503013fa9a0bf1ef4b907f5fec006c8f4000fdd21Michael J. Spencer#define FST_LIB_FSTLIB_H__
46d89275bc865e2b552836c7b33e636d4f86b8de6dDouglas Gregor
47025452fa0eda63e150cfaeebe64f0a19c96b3a06Douglas Gregor
482cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// Abstract FST classes
492cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#include <fst/fst.h>
502cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#include <fst/expanded-fst.h>
51677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor#include <fst/mutable-fst.h>
522cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor
532cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// Concrete FST classes
542cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#include <fst/compact-fst.h>
552cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#include <fst/const-fst.h>
562cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#include <fst/edit-fst.h>
572cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#include <fst/vector-fst.h>
582cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor
597d5c2f241c74e5f8d9ec492e8f9f268e5e9ae41fDouglas Gregor// FST algorithms and delayed FST classes
600af2ca4b6ddc788658069a0994941268ce250fc7Douglas Gregor#include <fst/arcsort.h>
612cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#include <fst/arc-map.h>
6295f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor#include <fst/closure.h>
63f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor#include <fst/compose.h>
6468a2eb0cc76267ba0615992fb5e0977853c397b2Douglas Gregor#include <fst/concat.h>
652cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#include <fst/connect.h>
662cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#include <fst/determinize.h>
675f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor#include <fst/difference.h>
686ad9ac097918fbdeb443ea7b99d4db9e49b28534Chris Lattner#include <fst/encode.h>
696ad9ac097918fbdeb443ea7b99d4db9e49b28534Chris Lattner#include <fst/epsnormalize.h>
70ebcbe1d3dc7d4f0c1f540a632fa0684dd0a857d5Sean Hunt#include <fst/equal.h>
71cbb67480094b3bcb5b715acd827cbad55e2a204cSean Hunt#include <fst/equivalent.h>
721a49d97d762570027863e9209af81d445e4f1502Douglas Gregor#include <fst/factor-weight.h>
731de05feeeafe5b215fe7617594a7076a5192a6e2Douglas Gregor#include <fst/intersect.h>
746a5a23f8e7fb65e028c8092bc1d1a1d9dfe2e9bcDouglas Gregor#include <fst/invert.h>
759818a1d443e97677dd3422305de9cc2b1fb2a8c1Argyrios Kyrtzidis#include <fst/map.h>
76668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor#include <fst/minimize.h>
7756ca35d396d8692c384c785f9aeebcf22563fe1eJohn McCall#include <fst/project.h>
7814f79002e58556798e86168c63e48d533287eda5Douglas Gregor#include <fst/prune.h>
79a71a7d8a1ce4474e7bdb680658fb58b6caf391d3Douglas Gregor#include <fst/push.h>
80668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor#include <fst/randequivalent.h>
81025452fa0eda63e150cfaeebe64f0a19c96b3a06Douglas Gregor#include <fst/randgen.h>
82c3632730cc83ed7b51f0ab5c38997ae5a9439b0cSebastian Redl#include <fst/rational.h>
83f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor#include <fst/relabel.h>
84c43b54cbc10654ed59de797898042e1a05265246Sebastian Redl#include <fst/replace.h>
85d527cc06d78fe5afa5f20105b51697637eb02c56Sebastian Redl#include <fst/replace-util.h>
86c3632730cc83ed7b51f0ab5c38997ae5a9439b0cSebastian Redl#include <fst/reverse.h>
87c3632730cc83ed7b51f0ab5c38997ae5a9439b0cSebastian Redl#include <fst/reweight.h>
88eb19485625c7529ffa644e10829533157a8e8d4fDaniel Dunbar#include <fst/rmepsilon.h>
890a0d2b179085a52c10402feebeb6db8b4d96a140Douglas Gregor#include <fst/rmfinalepsilon.h>
9057016dda61498294120b1a881d9e6606337b29d9Douglas Gregor#include <fst/shortest-distance.h>
912a82ca255b0f99f6201a75ed52b91fc024f6e9cfArgyrios Kyrtzidis#include <fst/shortest-path.h>
9211e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/statesort.h>
93c43b54cbc10654ed59de797898042e1a05265246Sebastian Redl#include <fst/state-map.h>
9411e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/synchronize.h>
95c43b54cbc10654ed59de797898042e1a05265246Sebastian Redl#include <fst/topsort.h>
9611e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/union.h>
97c43b54cbc10654ed59de797898042e1a05265246Sebastian Redl#include <fst/verify.h>
98571db7f0cb31789737be92fce1c1b738e6dbe795Sebastian Redl#include <fst/visit.h>
99571db7f0cb31789737be92fce1c1b738e6dbe795Sebastian Redl
10011e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis// Weights
101571db7f0cb31789737be92fce1c1b738e6dbe795Sebastian Redl#include <fst/weight.h>
1021eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump#include <fst/expectation-weight.h>
103c544ba09695e300f31355af342258bd57619e737Douglas Gregor#include <fst/float-weight.h>
104c544ba09695e300f31355af342258bd57619e737Douglas Gregor#include <fst/lexicographic-weight.h>
105c544ba09695e300f31355af342258bd57619e737Douglas Gregor#include <fst/pair-weight.h>
106c544ba09695e300f31355af342258bd57619e737Douglas Gregor#include <fst/power-weight.h>
107c544ba09695e300f31355af342258bd57619e737Douglas Gregor#include <fst/product-weight.h>
108c544ba09695e300f31355af342258bd57619e737Douglas Gregor#include <fst/random-weight.h>
109c544ba09695e300f31355af342258bd57619e737Douglas Gregor#include <fst/signed-log-weight.h>
110c544ba09695e300f31355af342258bd57619e737Douglas Gregor#include <fst/sparse-power-weight.h>
11111e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/sparse-tuple-weight.h>
11211e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/string-weight.h>
11311e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/tuple-weight.h>
11427ffa6caf965ef20fdef5ae23b81cdc3d05e7afbDouglas Gregor
11538295beb73db5f90bfcf31625fb81dbc3b96290aDouglas Gregor// Auxiliary classes for composition
11611e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/compose-filter.h>
11711e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/lookahead-filter.h>
1181eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump#include <fst/lookahead-matcher.h>
11957016dda61498294120b1a881d9e6606337b29d9Douglas Gregor#include <fst/matcher-fst.h>
12011e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/matcher.h>
12157016dda61498294120b1a881d9e6606337b29d9Douglas Gregor#include <fst/state-table.h>
12257016dda61498294120b1a881d9e6606337b29d9Douglas Gregor
12327ffa6caf965ef20fdef5ae23b81cdc3d05e7afbDouglas Gregor// Data structures
12438295beb73db5f90bfcf31625fb81dbc3b96290aDouglas Gregor#include <fst/heap.h>
12511e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/interval-set.h>
12611e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/queue.h>
1271eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump#include <fst/union-find.h>
1285f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor
1295f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor// Miscellaneous
1305f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor#include <fst/accumulator.h>
1315f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor#include <fst/add-on.h>
1325f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor#include <fst/arc.h>
1335f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor#include <fst/arcfilter.h>
1345f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor#include <fst/cache.h>
1355f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor#include <fst/complement.h>
1365f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor#include <fst/dfs-visit.h>
1371b2c3c0884e917ae5d59edde7d93b2af33c6a1b6Douglas Gregor#include <fst/generic-register.h>
1381b2c3c0884e917ae5d59edde7d93b2af33c6a1b6Douglas Gregor#include <fst/label-reachable.h>
1391b2c3c0884e917ae5d59edde7d93b2af33c6a1b6Douglas Gregor#include <fst/partition.h>
1401b2c3c0884e917ae5d59edde7d93b2af33c6a1b6Douglas Gregor#include <fst/properties.h>
1411b2c3c0884e917ae5d59edde7d93b2af33c6a1b6Douglas Gregor#include <fst/register.h>
1421b2c3c0884e917ae5d59edde7d93b2af33c6a1b6Douglas Gregor#include <fst/state-reachable.h>
1431b2c3c0884e917ae5d59edde7d93b2af33c6a1b6Douglas Gregor#include <iostream>
1441b2c3c0884e917ae5d59edde7d93b2af33c6a1b6Douglas Gregor#include <fstream>
1451b2c3c0884e917ae5d59edde7d93b2af33c6a1b6Douglas Gregor#include <sstream>
146bbf38319edd4eddc55ec273934e990d7e84991deDouglas Gregor#include <fst/string.h>
147bbf38319edd4eddc55ec273934e990d7e84991deDouglas Gregor#include <fst/symbol-table.h>
148bbf38319edd4eddc55ec273934e990d7e84991deDouglas Gregor#include <fst/symbol-table-ops.h>
149bbf38319edd4eddc55ec273934e990d7e84991deDouglas Gregor#include <fst/test-properties.h>
150bbf38319edd4eddc55ec273934e990d7e84991deDouglas Gregor#include <fst/util.h>
151bbf38319edd4eddc55ec273934e990d7e84991deDouglas Gregor
152bbf38319edd4eddc55ec273934e990d7e84991deDouglas Gregor
153bbf38319edd4eddc55ec273934e990d7e84991deDouglas Gregor#endif  // FST_LIB_FSTLIB_H__
154bbf38319edd4eddc55ec273934e990d7e84991deDouglas Gregor