Algebraic operations on automata. More...

#include <gfsmCompound.h>
#include <gfsmArcIndex.h>

Include dependency graph for gfsmAlgebra.h:

This graph shows which files directly or indirectly include this file:

Functions
gfsmClosure.c: closure (self-concatenation)
gfsmAutomaton *	gfsm_automaton_closure (gfsmAutomaton *fsm, gboolean is_plus)
gfsmAutomaton *	gfsm_automaton_n_closure (gfsmAutomaton *fsm, guint n)
gfsmAutomaton *	gfsm_automaton_optional (gfsmAutomaton *fsm)
gfsmComplement.c: Complementation and Completion
gfsmAutomaton *	gfsm_automaton_complement (gfsmAutomaton *fsm)
gfsmAutomaton *	gfsm_automaton_complement_full (gfsmAutomaton fsm, gfsmAlphabet alph)
gfsmAutomaton *	gfsm_automaton_complete (gfsmAutomaton fsm, gfsmAlphabet alph, gfsmStateId *sinkp)
gfsmConcat.c: Concatenation
gfsmAutomaton *	gfsm_automaton_n_concat (gfsmAutomaton fsm1, gfsmAutomaton fsm2, guint n)
gfsmAutomaton *	gfsm_automaton_concat (gfsmAutomaton fsm1, gfsmAutomaton _fsm2)
gfsmConnect.c: Co-Accessibility & Pruning
gfsmAutomaton *	gfsm_automaton_connect (gfsmAutomaton *fsm)
gfsmAutomaton *	gfsm_automaton_connect_fw (gfsmAutomaton fsm, gfsmBitVector visited)
gfsmAutomaton *	gfsm_automaton_connect_bw (gfsmAutomaton fsm, gfsmReverseArcIndex rarcs, gfsmBitVector *finalizable)
gfsmAutomaton *	gfsm_automaton_prune_states (gfsmAutomaton fsm, gfsmBitVector wanted)
gfsmDifference.c: Difference
gfsmAutomaton *	gfsm_automaton_difference (gfsmAutomaton fsm1, gfsmAutomaton fsm2)
gfsmAutomaton *	gfsm_automaton_difference_full (gfsmAutomaton fsm1, gfsmAutomaton fsm2, gfsmAutomaton *diff)
gfsmIntersect.c: Intersection
gfsmAutomaton *	gfsm_automaton_intersect (gfsmAutomaton fsm1, gfsmAutomaton fsm2)
gfsmAutomaton *	gfsm_automaton_intersect_full (gfsmAutomaton fsm1, gfsmAutomaton fsm2, gfsmAutomaton intersect, gfsmStatePairEnum spenum)
gfsmStateId	gfsm_automaton_intersect_visit_ (gfsmStatePair sp, gfsmAutomaton fsm1, gfsmAutomaton fsm2, gfsmAutomaton fsm, gfsmStatePairEnum spenum, gfsmComposeFlags flags)
gfsmMinimize.c: Minimization
gfsmAutomaton *	gfsm_automaton_minimize (gfsmAutomaton *fsm)
gfsmAutomaton *	gfsm_automaton_minimize_full (gfsmAutomaton *fsm, gboolean rmeps)
gfsmAutomaton *	gfsm_automaton_compact (gfsmAutomaton *fsm)
gfsmAutomaton *	gfsm_automaton_compact_full (gfsmAutomaton *fsm, gboolean rmeps)
gfsmProject.c: Projection & Inversion
gfsmAutomaton *	gfsm_automaton_invert (gfsmAutomaton *fsm)
gfsmAutomaton *	gfsm_automaton_project (gfsmAutomaton *fsm, gfsmLabelSide which)
gfsmProduct.c: Cartesian Product
gfsmAutomaton *	gfsm_automaton_product (gfsmAutomaton fsm1, gfsmAutomaton fsm2)
gfsmAutomaton *	gfsm_automaton_product2 (gfsmAutomaton fsm1, gfsmAutomaton fsm2)
gfsmReplace.c: Replacement
gfsmAutomaton *	gfsm_automaton_replace (gfsmAutomaton fsm1, gfsmLabelVal lo, gfsmLabelVal hi, gfsmAutomaton fsm2)
gfsmAutomaton *	gfsm_automaton_insert_automaton (gfsmAutomaton fsm1, gfsmStateId q1from, gfsmStateId q1to, gfsmAutomaton fsm2, gfsmWeight w)
gfsmReverse.c: Reversal
gfsmAutomaton *	gfsm_automaton_reverse (gfsmAutomaton *fsm)
gfsmRmEpsilon.c: Epsilon Removal
gfsmAutomaton *	gfsm_automaton_rmepsilon (gfsmAutomaton *fsm)
gfsmSigma.c: Alphabet Recognizer
gfsmAutomaton *	gfsm_automaton_sigma (gfsmAutomaton fsm, gfsmAlphabet abet)
gfsmUnion.c: Union
gfsmAutomaton *	gfsm_automaton_union (gfsmAutomaton fsm1, gfsmAutomaton fsm2)

gfsmCompose.c: Composition
enum	gfsmComposeFlagsE { gfsmCFEfsm1NeedsArcSort = 0x1, gfsmCFEfsm2NeedsArcSort = 0x2 }
	Enum type for low-level flags to gfsm_automaton_compose_visit_state_() More...
typedef guint32	gfsmComposeFlags
gfsmAutomaton *	gfsm_automaton_compose (gfsmAutomaton fsm1, gfsmAutomaton fsm2)
gfsmAutomaton *	gfsm_automaton_compose_full (gfsmAutomaton fsm1, gfsmAutomaton fsm2, gfsmAutomaton composition, gfsmComposeStateEnum spenum)
void	gfsm_automaton_compose_visit_ (gfsmStateId qid, gfsmAutomaton fsm1, gfsmAutomaton fsm2, gfsmAutomaton fsm, gfsmComposeStateEnum spenum, GArray spenumr, GQueue queue, gfsmComposeFlags flags)

gfsmDeterminize.c: Determinization
#define	gfsm_automaton_determinise(fsm) gfsm_automaton_determinize(fsm)
#define	gfsm_automaton_determinise_full(nfa, dfa) gfsm_automaton_determinize_full((nfa),(dfa))
gfsmAutomaton *	gfsm_automaton_determinize (gfsmAutomaton *fsm)
gfsmAutomaton *	gfsm_automaton_determinize_full (gfsmAutomaton nfa, gfsmAutomaton dfa)

Detailed Description

Todo:

bestpath() ?

encode() ?

equiv() ?

deterministic union ?

xerox-style property-savvy lookup()?

Macro Definition Documentation

#define gfsm_automaton_determinise ( fsm ) gfsm_automaton_determinize(fsm)

Alias for gfsm_automaton_determinize()

#define gfsm_automaton_determinise_full	(	nfa,
		dfa
	)	gfsm_automaton_determinize_full((nfa),(dfa))

Alias for gfsm_automaton_determinize_full()

Typedef Documentation

typedef guint32 gfsmComposeFlags

flags for gfsm_automaton_compose_visit_state_()

Enumeration Type Documentation

enum gfsmComposeFlagsE

Enumerator:

gfsmCFEfsm1NeedsArcSort
gfsmCFEfsm2NeedsArcSort

Function Documentation

gfsmAutomaton* gfsm_automaton_closure	(	gfsmAutomaton *	fsm,
		gboolean	is_plus
	)

Compute transitive or reflexive-&-transitive closure of fsm.

Note: Destructively alters fsm .

Parameters

fsm	Automaton
is_plus	Which type of closure to compute: TRUE transitive closure FALSE reflexive & transitive closure

Returns: modified fsm

gfsmAutomaton* gfsm_automaton_n_closure	(	gfsmAutomaton *	fsm,
		guint	n
	)

Compute n-ary closure of fsm.

Note: Destructively alters fsm.

Parameters

fsm	Automaton
n	Number of repetitions

Returns: modified fsm

gfsmAutomaton* gfsm_automaton_optional ( gfsmAutomaton * fsm )

Make fsm optional.

Note: Destructively alters fsm

Parameters

fsm Automaton

Returns: modified fsm

gfsmAutomaton* gfsm_automaton_complement ( gfsmAutomaton * fsm )

Compute the lower-side complement of fsm with respect to its own lower alphabet.

Note: Destructively alters fsm

Parameters

fsm Acceptor

Returns: fsm

gfsmAutomaton* gfsm_automaton_complement_full	(	gfsmAutomaton *	fsm,
		gfsmAlphabet *	alph
	)

Compute the lower-side complement of fsm with respect to the alphabet alph, which should contain all of the lower-labels from fsm.

Note: Destructively alters fsm.

Parameters

fsm	Acceptor
alph	Alphabet with respect to which to compute complement.

Returns: fsm

gfsmAutomaton* gfsm_automaton_complete	(	gfsmAutomaton *	fsm,
		gfsmAlphabet *	alph,
		gfsmStateId *	sinkp
	)

Complete the lower side of automaton fsm with respect to the alphabet alph by directing "missing" arcs to the (new) state with id *sink.

Note: Destructively alters fsm.

Parameters

fsm	Acceptor
alpha	Alphabet with respect to which fsm is to be completed
sinkp	Pointer to a variable which on completion contains the Id of a (new) non-final sink state

Returns: fsm

gfsmAutomaton* gfsm_automaton_compose	(	gfsmAutomaton *	fsm1,
		gfsmAutomaton *	fsm2
	)

Compute the composition of fsm1 with fsm2 (upper-side of fsm1 intersection with lower-side of fsm2).

Parameters

fsm1	Lower-middle transducer
fsm2	Middle-upper transducer

Returns: Altered fsm1

Note

Pseudo-destructive on fsm1.
Runtime efficiency can be greatly improved if fsm1 is sorted on upper labels (gfsmASMUpper) and fsm2 is sorted on lower labels (gfsmASMLower).

See Also: gfsm_automaton_compose_full()

gfsmAutomaton* gfsm_automaton_compose_full	(	gfsmAutomaton *	fsm1,
		gfsmAutomaton *	fsm2,
		gfsmAutomaton *	composition,
		gfsmComposeStateEnum *	spenum
	)

Compute the composition of two transducers fsm1 and fsm2 into the transducer composition.

Parameters

fsm1	Lower-middle transducer
fsm2	Middle-upper transducer
composition	Lower-upper transducer. May be passed as NULL to create a new automaton.
spenum	Mapping from (fsm1,fsm2,filter) gfsmComposeState s to composition (gfsmStateId)s, if it is passed as NULL, a temporary enum will be created and freed.

See Also: Mohri, Pereira, and Riley (1996), "Weighted Automata in Text and Speech Processing", In: Proc. ECAI '96, John Wiley & Sons, Ltd.

Returns: composition

void gfsm_automaton_compose_visit_	(	gfsmStateId	qid,
		gfsmAutomaton *	fsm1,
		gfsmAutomaton *	fsm2,
		gfsmAutomaton *	fsm,
		gfsmComposeStateEnum *	spenum,
		GArray *	spenumr,
		GQueue *	queue,
		gfsmComposeFlags	flags
	)

Guts for gfsm_automaton_compose()

Returns: (new) StateId for sp

gfsmAutomaton* gfsm_automaton_n_concat	(	gfsmAutomaton *	fsm1,
		gfsmAutomaton *	fsm2,
		guint	n
	)

Append fsm2 onto the end of fsm1 n times.

Note: Destructively alters fsm1.

Parameters

fsm1	Automaton
fsm2	Automaton

Returns: fsm1

gfsmAutomaton* gfsm_automaton_concat	(	gfsmAutomaton *	fsm1,
		gfsmAutomaton *	_fsm2
	)

Append _fsm2 onto the end of fsm1.

Note: Destructively alters fsm1.

Parameters

fsm1	Automaton
fsm2	Automaton

Returns: fsm1

gfsmAutomaton* gfsm_automaton_connect ( gfsmAutomaton * fsm )

Remove non-coaccessible states from fsm. Calls gfsm_automaton_connect_fw() and gfsm_automaton_connect_bw()

Note: Destructively alters fsm

Parameters

fsm Automaton

Returns: modified fsm

gfsmAutomaton* gfsm_automaton_connect_fw	(	gfsmAutomaton *	fsm,
		gfsmBitVector *	visited
	)

Remove non root-accessible states from fsm. Called by gfsm_automaton_connect()

Note: Destructively alters fsm

Parameters

fsm	Automaton
visited	Bit-vector for traversal. Should have all bits set to zero. If passed as NULL, a new bit-vector will be created and freed.

Returns: modified fsm

gfsmAutomaton* gfsm_automaton_connect_bw	(	gfsmAutomaton *	fsm,
		gfsmReverseArcIndex *	rarcs,
		gfsmBitVector *	finalizable
	)

Remove non-finalizable states from fsm. Called by gfsm_automaton_connect().

Note: Destructively alters fsm

Parameters

fsm	Automaton
rarcs	Reverse arc-index as returned by gfsm_automaton_reverse_arc_index(). If passed as NULL, gfsm_automaton_reverse_arc_index() will be called on a temporary arc index.
finalizable	Bit-vector for traversal. Should have all bits set to zero. If passed as NULL, a new bit-vector will be created and freed.

Returns: modified fsm

gfsmAutomaton* gfsm_automaton_prune_states	(	gfsmAutomaton *	fsm,
		gfsmBitVector *	wanted
	)

Utility for gfsm_automaton_connect_fw() and gfsm_automaton_connect_bw(). Prunes states from fsm whose id bit is not set in want

Parameters

fsm	Automaton
wanted	Bit-vector indexed by state id: bit id should be unset iff state id is to be removed.

Returns: modified fsm

gfsmAutomaton* gfsm_automaton_determinize ( gfsmAutomaton * fsm )

Determinize acceptor fsm

Pseudo-destructive on fsm
Epsilon is treated like any other symbol.
Arc labels are treated as (input,output) pairs for purposes of state-equivalence-class construction: this may not be what you want.

Parameters

fsm Automaton

Returns: altered fsm

See Also: gfsm_automaton_determinize_full()

gfsmAutomaton* gfsm_automaton_determinize_full	(	gfsmAutomaton *	nfa,
		gfsmAutomaton *	dfa
	)

Determinize automaton nfa to dfa

Epsilon is treated like any other symbol.
Arc labels are treated as (input,output) pairs.

Parameters

nfa	non-deterministic acceptor
dfa	deterministic acceptor to be constructed May be passed as `NULL` to create a new automaton.

Returns: dfa

gfsmAutomaton* gfsm_automaton_difference	(	gfsmAutomaton *	fsm1,
		gfsmAutomaton *	fsm2
	)

Remove language of acceptor fsm2 from acceptor fsm1.

Pseudo-destructively alters fsm1.
Really just an alias for intersect_full(fsm1,fsm2,NULL)

Parameters

fsm1	Acceptor
fsm2	Acceptor

Returns: fsm1

gfsmAutomaton* gfsm_automaton_difference_full	(	gfsmAutomaton *	fsm1,
		gfsmAutomaton *	fsm2,
		gfsmAutomaton *	diff
	)

Compute difference of acceptors (fsm1 - fsm2) into acceptor diff-

Note: Really just an alias for intersect_full(fsm1,complement(clone(fsm2)),diff).

Parameters

fsm1	Acceptor
fsm2	Acceptor
diff	Output (difference) acceptor, may be passed as `NULL` to implicitly create a new automaton.

Returns: (possibly new) difference automaton diff

gfsmAutomaton* gfsm_automaton_intersect	(	gfsmAutomaton *	fsm1,
		gfsmAutomaton *	fsm2
	)

Compute the intersection of two acceptors fsm1 and fsm2 (lower-side intersection).

Note: Pseudo-destructive on fsm1.

Parameters

fsm1	Acceptor
fsm2	Acceptor

Returns: fsm1.

gfsmAutomaton* gfsm_automaton_intersect_full	(	gfsmAutomaton *	fsm1,
		gfsmAutomaton *	fsm2,
		gfsmAutomaton *	intersect,
		gfsmStatePairEnum *	spenum
	)

Compute the intersection of two acceptors fsm1 and fsm2 into the acceptor intersect.

Parameters

fsm1	Acceptor
fsm2	Acceptor
intersect	Output acceptor, may be `NULL` to create a new automaton.
spenum	Mapping from (fsm1,fsm2) (gfsmStatePair)s to intersect (gfsmStateId)s, may be NULL to use a temporary mapping.

Returns: intersect.

gfsmStateId gfsm_automaton_intersect_visit_	(	gfsmStatePair	sp,
		gfsmAutomaton *	fsm1,
		gfsmAutomaton *	fsm2,
		gfsmAutomaton *	fsm,
		gfsmStatePairEnum *	spenum,
		gfsmComposeFlags	flags
	)

Guts for gfsm_automaton_intersect()

Returns: (new) gfsmStateId for sp

gfsmAutomaton* gfsm_automaton_minimize ( gfsmAutomaton * fsm )

Minimize an automaton, treating transducers as pair-acceptors. Just a wrapper for gfsm_automaton_minimimize_full(fsm,TRUE).

Note: pseudo-destructive on fsm

Parameters

fsm	Automaton to minimize.

Returns: minimized fsm

gfsmAutomaton* gfsm_automaton_minimize_full	(	gfsmAutomaton *	fsm,
		gboolean	rmeps
	)

Quasi-minimization using Brzozowski (1963) algorithm, with optional epsilon-removal.

Note: pseudo-destructive on fsm

See Also: J. A. Brzozowski, "Canonical regular expressions and minimal state graphs for definite events", In: Proc. Sympos. Math. Theory of Automata (New York, 1962), Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, NY, pp. 529–561, URL: http://www.ams.org/mathscinet-getitem?mr=0175719

Parameters

fsm	Automaton to minimize.
rmeps	Whether to include epsilon-removal (true minimization) or not (quasi-minimization)

Returns: (quasi-)minimized fsm

gfsmAutomaton* gfsm_automaton_compact ( gfsmAutomaton * fsm )

Heuristically compact an automaton. Really just a wrapper for gfsm_automaton_compact_full(fsm,TRUE).

Note: pseudo-destructive on fsm

Parameters

fsm	Automaton to compact.

Returns: compacted fsm

gfsmAutomaton* gfsm_automaton_compact_full	(	gfsmAutomaton *	fsm,
		gboolean	rmeps
	)

Heuristic compaction like gfsmencode fsm KEY | gfsmminimize | gfsmdecode - KEY

Note: destructively alters fsm

Parameters

fsm	automaton to compact
rmeps	Whether to include epsilon-removal in encoded-acceptor minimization step

Returns: compacted fsm

gfsmAutomaton* gfsm_automaton_invert ( gfsmAutomaton * fsm )

Invert upper and lower labels of an automaton.

Note: Destructively alters fsm.

Parameters

fsm	Transducer

Returns: fsm

gfsmAutomaton* gfsm_automaton_project	(	gfsmAutomaton *	fsm,
		gfsmLabelSide	which
	)

Project one "side" (lower or upper) of fsm

Note: Destructively alters fsm

Parameters

fsm	Transducer
which	Which label side to project. gfsmLSLower project lower side gfsmLSUpper project upper side (default)

Returns: modified fsm

gfsmAutomaton* gfsm_automaton_product	(	gfsmAutomaton *	fsm1,
		gfsmAutomaton *	fsm2
	)

Compute Cartesian product of acceptors fsm1 and fsm2.

Note: Destructively alters fsm1.

Parameters

fsm1	Acceptor (lower)
fsm2	Acceptor (upper)

Returns: fsm1 (transducer)

See Also: gfsm_automaton_product2()

gfsmAutomaton* gfsm_automaton_product2	(	gfsmAutomaton *	fsm1,
		gfsmAutomaton *	fsm2
	)

Compute Cartesian product of acceptors fsm1 and fsm2.

Note: Destructively alters fsm1 and fsm2.

Parameters

fsm1	Acceptor (lower)
fsm2	Acceptor (upper)

Returns: fsm1

gfsmAutomaton* gfsm_automaton_replace	(	gfsmAutomaton *	fsm1,
		gfsmLabelVal	lo,
		gfsmLabelVal	hi,
		gfsmAutomaton *	fsm2
	)

Replace label-pair (lo,hi) with fsm2 in fsm1 .

Note: Destructively alters fsm.

Parameters

fsm1	Automaton
lo	lower label or gfsmNoLabel to ignore lower labels
hi	upper label or gfsmNoLabel to ignore upper labels

Returns: modified fsm1

gfsmAutomaton* gfsm_automaton_insert_automaton	(	gfsmAutomaton *	fsm1,
		gfsmStateId	q1from,
		gfsmStateId	q1to,
		gfsmAutomaton *	fsm2,
		gfsmWeight	w
	)

Insert automaton fsm2 into fsm1 between states q1from and q1to with weight w.

Note: Destructively alters fsm1.

Parameters

fsm1	Automaton into which fsm2 is inserted
fsm2	Automaton to be inserted
q1from	Source state for inserted automaton in fsm1
q1to	Final state for inserted automaton in fsm1
w	Weight to add to final arcs for translated fsm2 in fsm1

Returns: modified fsm1

gfsmAutomaton* gfsm_automaton_reverse ( gfsmAutomaton * fsm )

Reverse an automaton fsm.

Note: Destructively alters fsm.

Parameters

fsm Automaton

Returns: fsm

gfsmAutomaton* gfsm_automaton_rmepsilon ( gfsmAutomaton * fsm )

Remove epsilon arcs from fsm.

Destructively alters fsm.
Implementation of incremental algorithm from Hanneforth & de la Higueara (2010).

Warning: negative-cost epsilon cycles in fsm will cause an infinite loop!

See Also: T. Hanneforth & C. de la Higuera (2010), "ε-Removal by Loop Reduction for Finite-state Automata over Complete Semirings." In T. Hanneforth and G. Fanselow, editors, Language and Logos: Studies in Theoretical and Computational Linguistics, volume 72 of Studia grammatica. Akademie Verlag, Berlin. ISBN 978-3-05-004931-1.

Parameters

fsm Automaton

Returns: fsm

gfsmAutomaton* gfsm_automaton_sigma	(	gfsmAutomaton *	fsm,
		gfsmAlphabet *	abet
	)

Make fsm an identity-transducer for alphabet abet

Note: Destructively alters fsm.

Parameters

fsm Automaton

Returns: fsm

gfsmAutomaton* gfsm_automaton_union	(	gfsmAutomaton *	fsm1,
		gfsmAutomaton *	fsm2
	)

Add the language or relation of fsm2 to fsm1.

Note: Destructively alters fsm1

Parameters

fsm1	Automaton
fsm2	Automaton

Returns: fsm1

Functions

gfsmCompose.c: Composition

gfsmDeterminize.c: Determinization

Detailed Description

Macro Definition Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation