Difference: HfstAPIGeneralizedRestrictionLayerOLD (1 vs. 11)

Revision 112009-09-30 - ErikAxelson

Line: 1 to 1
 
META TOPICPARENT name="HfstHome"

HFST: API for Generalized Restriction (GR) and Predicate Logic in FST Calculus

Line: 103 to 103
 

Function Supporting Substring Variables

Changed:
<
<
These functions are implemented in a latter stage. These are currently moved to HfstAPIGeneralizedRestrictionLayer2 in order to prioritize the work.
>
>
These functions are implemented in a latter stage. These are currently moved to HfstAPIGeneralizedRestrictionLayer2OLD in order to prioritize the work.
 

References

Line: 139 to 139
 --> -- AnssiYliJyra - 06 Oct 2008
Changed:
<
<
META TOPICMOVED by="AnssiYliJyra" date="1223288854" from="KitWiki.HfstGeneralizedRestrictionAPI" to="KitWiki.HfstAPIGeneralizedRestrictionLayer"
>
>
META TOPICMOVED by="eaxelson" date="1254311494" from="KitWiki.HfstAPIGeneralizedRestrictionLayer" to="KitWiki.HfstAPIGeneralizedRestrictionLayerOLD"

Revision 102009-05-21 - AnssiYliJyra

Line: 1 to 1
 
META TOPICPARENT name="HfstHome"

HFST: API for Generalized Restriction (GR) and Predicate Logic in FST Calculus

Added:
>
>
THIS TOPIC IS NOT UP TO DATE
 

Introduction

Purpose of the layer

This extension to the basic HFST API provides support for new letter-FST operations that are useful for compilation of

Revision 92008-10-14 - AnssiYliJyra

Line: 1 to 1
 
META TOPICPARENT name="HfstHome"

HFST: API for Generalized Restriction (GR) and Predicate Logic in FST Calculus

Line: 94 to 94
 
OvertFstHandle connect_with_concatenation (OvertFstHande e, OvertFstHande f) Combines two overt FSTs under concatenation.    
OvertFstHandle connect_with_and (OvertFstHande e, OvertFstHande f) Combines two overt FSTs under conjunction.    
OvertFstHandle connect_with_relative_complement (OvertFstHande e, OvertFstHande f) Combine two overt FSTs as e ∪ ¬f.    
Changed:
<
<
OvertFstHandle quantify_existentially (VarHandle m, OvertFstHandle φ) Restricts φ to those strings that contain an m and hides then m in φ,
or computes (∃ x)φ(x).
   
>
>
OvertFstHandle quantify_existentially (VarHandle m, OvertFstHandle φ) Restricts φ to those strings that contain an m and hides then m in φ by removing them like epsilons,
i.e. computes (∃ x)φ(x).
   
TransducerHandle quantify_existentially_all (OvertFstHande e) Removes all auxiliary symbols.    
 
OvertFstHandle quantify_universally (VarHandle m, OvertFstHandle φ) Restricts x to all substrings in φ by evaluating
    Σ* <x> Σ* <x> Σ*  =x>  φ
i.e. computes ¬ ((∃ x) ¬φ(x)) that is the same as (∀ x)φ(m).
   
Changed:
<
<
OvertFstHandle quantify_universally_all (OvertFstHandle φ) The essential part of the ordinary GR operation that removes all variables at once like repeatly applying quantify_universally for all of them.    
>
>
TransducerHandle quantify_universally_all (OvertFstHandle φ) The essential part of the ordinary GR operation that removes all variables at once like repeatly applying quantify_universally for all of them.    
 

Function Supporting Substring Variables

Revision 82008-10-14 - AnssiYliJyra

Line: 1 to 1
 
META TOPICPARENT name="HfstHome"

HFST: API for Generalized Restriction (GR) and Predicate Logic in FST Calculus

Line: 17 to 17
 

Basic Notions

Auxiliary Marker Symbols

Changed:
<
<
  1. The basic and common notion in both streams is the notion of an auxiliary symbol that is used to indicate a boundary of a substring. This symbol has two names: a diamond and variable symbol (). More such symbols can be numbered or named according to letters using different notational conventions: 1, ◊2,..., <x>, <y>, ... (x), (y),..., x, y, .... These auxiliary symbols occur in strings of marker-augmented FSTs that we call below over FSTs (interfaced through OvertFstHandle). The data type of an uncompiled generalized restriction is OvertFstPair.
  2. In addition to those e.g. dozen auxiliary symbols that have been employed by an application programmer, we need to prepare for hundreds of such auxiliary symbols that are created by special algorithms that speed up the compilation of the GR operation. These symbols are added in certain paths in order to make FSTs look simpler. Their number can be large since we want to more auxiliary symbols when we have a weighted GR operation in the future. For example, nondeterministic FST can be transformed to a deterministic one by adding such auxiliary symbols. Regardless of the purpose, the auxiliary symbols have the same type and it is interfaced through a VarHandle.
  3. There are many ways to use auxiliary markers. All these should be supported: (i) it occurs only once in every path of over FSTs, (ii) it occurs twice, (iii) it occurs 4 times, (iv) it occurs freely in specified positions. They can be removed one by one or once for all. Accordingly, auxiliary symbols are quite similar to normal symbols (or keys).
  4. Overt FSTs keep track of the known auxiliary markers that vary from FST to FST even if they could share the same key table. Those symbols that an FST does not know need to be added by harmonization when the FST is combined under intersection with other FSTs. There, loops for unknown auxiliaries are simply added.
  5. The complementation of over FST is computed w.r.t. the universal language over all pairs of known and unknown normal symbols and all the identity pairs of known auxiliary symbols.
>
>
Overt FSTs keep track of the set of the known auxiliary markers (or their keys).
  1. The basic and common notion in both streams is the notion of an auxiliary symbol that is used to indicate a boundary of a substring. This symbol has two names: a diamond and variable symbol (). More such symbols can be numbered or named according to letters using different notational conventions: 1, ◊2,..., <x>, <y>, ... (x), (y),..., x, y, .... These auxiliary symbols occur in strings of marker-augmented FSTs that we call overt FSTs (interfaced through OvertFstHandle). The data type of an uncompiled generalized restriction is OvertFstPair.
  2. The size of th auxiliary symbol alphabet may vary dynamically.
    1. Most applications use only one or two kinds of auxiliary symbols, but they may need a few more (a few dozens of them).
    2. In addition to these auxiliary symbols that are employed by an application programmer, we need to prepare for hundreds of such auxiliary symbols that are created by special algorithms that speed up the compilation of the GR operation. These symbols are added in certain paths in order to make FSTs look simpler. It is not yet certain whether these symbols are internalized to an algorithm or whether they need to be stored to the marker alphabet of the overt FSTs.
    3. The number may be even larger in the future when we have a weighted GR operation. Each rule and non-zero weight in the representation of the rules may need a separate auxiliary symbol. For example, a nondeterministic FST can often be transformed to a deterministic one by adding such auxiliary symbols.
  3. Unknown auxiliary symbols have to added by harmonization in some situations:
    1. When an FST is combined under intersection with other FSTs: loops for unknown auxiliaries are simply added to all FSTs that are being combined under intersection.
    2. The complement or relative complement of an overt FST is computed w.r.t. the universal language over all pairs of known and unknown normal symbols and all the identity pairs of known auxiliary symbols.

All auxiliary symbol are neither used to mark things in similar ways and they are not used to mark similar things.

  1. The number of auxiliary symbols in the strings may vary since there are many ways ("usage modes") to use auxiliary markers. All these should be supported:
    1. It occurs in specified positions and is used as a joiner rather than a substring marker.
    2. It occurs a bounded number of times (typically 2) and mark substrings.
    3. It occurs freely in specified positions that may be finite of infinit.
  2. All auxiliary symbols used in the current layer have are interfaced through a VarHandle.
    1. Each VarHandle contains a Key. In transitions, these Keys are used. The auxiliary symbols can be removed from FSTs one by one or once for all. Accordingly, auxiliary symbols are quite similar to keys of normal symbols.
    2. The VarHandle that is stored to the marker alphabet of over FSTs containts additional information on usage mode of the symbol.
  3. The functions in the GR layer may test that the relevant VarHandles have a correct usage mode.
    1. The current layer supports only one kind of auxiliary symbols: those that are used in pairs to mark substrings.
    2. Yli-Jyrä (2007a, 2007b) and Yli-Jyrä and Koskenniemi (2004) already employ auxiliary symbols that do not occur in pairs but as a joiners or freely in specified positions.

The total set of possible pairs have to be defined somehow when a complement of an overt FST is computed.

  1. Access to related =other=-symbol (or key) conventions would make the complementation more compact and efficient. Therefore, the layer supporting unknown keys and pairs would be below the current layer.
  2. We do not need an =other=-symbol that would account for unknown auxiary markers, since unknown auxiliary symbols are treated as epsilons except in intersection and relative complementation.
 

Nondeterministic Letter Transducers

Often letter transducers are kept as deterministic and minimal. However, in the case of overt FSTs, we may want to avoid determinization of intermediate results.
Changed:
<
<

Operations, Functions and Related Layers

  1. VarHandle can contain a KeyHandle rather than a SymbolHandle and it probably more feasible to implement that way.
  2. Excepting the harmonization and carrying the auxiliary symbol alphabet, most of the functionalities of this layer is based just normal FST operations provided by the TransducerLayer. Accordingly, the large number of operations in the current layer does not imply much programming.
  3. The functions in the current layer are all derived and their are mostly of similar complexity. We see all operations that use only overt FSTs as primitive while those build on over FST pairs are derived.
  4. However, the total set of possible pairs have to be defined somehow. Therefore, optional access to related =other=-symbol (or key) conventions would make the complementation more compact and efficient.
>
>

Overview of this Layer

 
Changed:
<
<

Data Types

>
>
Excepting the harmonization and carrying the auxiliary symbol alphabet, most of the functionalities of this layer is based on normal FST operations provided by the TransducerLayer. Accordingly, the large number of operations in the current layer does not imply much programming.
 
Type Comment hfst-lexc hfst-twolc
Line: 42 to 59
 
OvertFstPair a pair of FSTs using variables    
TransducerHandle an HFST transducer without variable symbols    
Changed:
<
<

Function Primitives

Definition of Substring Variables and other Diamond Symbols

>
>
The current layer contains a few sets of functions:
  1. Those that need to assume a particular usage of auxiliary symbols that are given as VarHandle parameters:
    • functions for joiner variables (minimun level of support)
    • functions for substring variables
    • functions for auxiliary symbols that occur freely in specified positions
  2. Those that operate overt FSTs and their pairs without paying attention to the usage modes of the known auxiliary symbols.

Functions Supporting Joiner Variables

Creating New Joiner Variables

 
Type Function Comment hfst-lexc hfst-twolc
Changed:
<
<
VarHandle create_var_type2 () Create a FO variable used for boundaries of a substring    
>
>
VarHandle create_var_type1 () Create a FO variable used for a boundary between two substrings    
 
VarSetHandle create_var_set () Create an empty set of FO variables    
VarSetHandle insert_var (VarSetHandle s, VarHandle x) Insert an FO variable to set s    
Changed:
<
<

Functions That Relate Substring Variables to Variable-Free Conditions

Type Function Comment hfst-lexc hfst-twolc
OvertFstHandle var_is_member (VarHandle x, TransducerHandle t) Asserts that substring x is recognized by t.    
OvertFstHandle var_partition (VarHandle v, VarHandle x, VarHandle y) Asserts that string is partitioned into substrings v, x and y.    
OvertFstHandle var_is_substring_with_context (VarHandle x, TransducerHandle rc, TransducerHandle cntr, TransducerHandle rc, bool padded) Asserts that x is substring of strings in cntr that is surrounded by (padded) contexts lc and rc.    
OvertFstHandle var_has_context (VarHandle x, TransducerHandle lc, TransducerHandle rc, bool padded) Asserts that substring x is surrounded by (padded) contexts lc and rc.    
OvertFstHandle var_precedes (VarHandle x, TransducerHandle rc, bool padded) Asserts that substring x precedes (padded) right context rc.    
OvertFstHandle var_follows (VarHandle x, TransducerHandle lc, bool padded) Asserts that substring x follows (padded) left context lc.    
(this table is subject to minor changes)

Functions That Compare or Rename Substring Variables

>
>

Functions That Relate Joiner Variables to FSTs

 
Type Function Comment hfst-lexc hfst-twolc
Changed:
<
<
OvertFstHandle var_embeds (VarHandle x, VarHandle y) Asserts that substring x contains substring y.    
OvertFstHandle var_equals (VarHandle x, VarHandle y) Asserts that substrings x and y are equal.    
OvertFstHandle var_starts_simultaneously (VarHandle x, VarHandle y) Asserts that substrings x and y are equal.    
OverFstHandle var_ends_simultaneously (VarHandle x, VarHandle y) Asserts that substrings x and y are equal.    
OvertFstHandle var_starts_before (VarHandle x, VarHandle y) Asserts that substring x starts before substring y.    
OvertFstHandle var_ends_before (VarHandle x, VarHandle y) Asserts that substring x ends before substring y.    
OvertFstHandle var_comes_before (VarHandle x, VarHandle y) Asserts that substring x occurs ends before substring y starts.    
OvertFstHandle var_has_overlap (VarHandle x, VarHandle y) Asserts that substring x and substring y are not disjoint (Hulden 2008).    
OvertFstHandle var_is_prefix_of (VarHandle x, VarHandle y) Asserts that substring x is prefix of y.    
OvertFstHandle var_is_suffix_of (VarHandle x, VarHandle y) Asserts that substring x is suffix of y.    
OvertFstHandle rename_var (VarHandle x, VarHandle y, OvertFstHandle ψ) Makes α transformation for overt FST ψ by replacing variable x with variable y.    
>
>
OvertFstHandle var_create_joiner_fst (VarHandle x, TransducerHandle t) Asserts that position x is a boundary between empty prefix and empty suffix.    
 

Functions That Implement Logical Connectors and Quantifiers

Type Function Comment hfst-lexc hfst-twolc
Changed:
<
<
OvertFstHandle connect_with_concatenation (OvertFstHande e, OvertFstHande f) Combine two overt FSTs under contenation.    
OvertFstHandle connect_with_and (OvertFstHande e, OvertFstHande f) Combine two overt FSTs under conjunction.    
OvertFstHandle connect_with_or (OvertFstHande e, OvertFstHande f) Combine two overt FSTs under disjunction.    
OvertFstHandle connect_with_xor (OvertFstHande e, OvertFstHande f) Combine two overt FSTs under exclusive disjunction.    
OvertFstHandle connect_with_not (OvertFstHande e) Negate an overt FST.    
OvertFstHandle connect_with_arrow (OvertFstHande e, OvertFstHande f) Combine two overt FSTs with material implication.    
OvertFstHandle quantify_existentially (VarHandle m, OvertFstHandle φ) Hides diamond x in φ,
or computes (∃ x)φ(x).
   
OvertFstHandle quantify_universally (VarHandle m, OvertFstHandle φ) Restrict x to all substrings in φ by evaluating
    Σ* <x> Σ* <x> Σ*  =x>  φ
or computes (∀ x)φ(x).
   
>
>
OvertFstHandle convert_to_overt_fst (TransducerHande e) Rises the type of a transducer to an overt FST.    
OvertFstHandle connect_with_concatenation (OvertFstHande e, OvertFstHande f) Combines two overt FSTs under concatenation.    
OvertFstHandle connect_with_and (OvertFstHande e, OvertFstHande f) Combines two overt FSTs under conjunction.    
OvertFstHandle connect_with_relative_complement (OvertFstHande e, OvertFstHande f) Combine two overt FSTs as e ∪ ¬f.    
OvertFstHandle quantify_existentially (VarHandle m, OvertFstHandle φ) Restricts φ to those strings that contain an m and hides then m in φ,
or computes (∃ x)φ(x).
   
OvertFstHandle quantify_universally (VarHandle m, OvertFstHandle φ) Restricts x to all substrings in φ by evaluating
    Σ* <x> Σ* <x> Σ*  =x>  φ
i.e. computes ¬ ((∃ x) ¬φ(x)) that is the same as (∀ x)φ(m).
   
OvertFstHandle quantify_universally_all (OvertFstHandle φ) The essential part of the ordinary GR operation that removes all variables at once like repeatly applying quantify_universally for all of them.    
 
Changed:
<
<

Functions That Construct, Combine and Compile GR Rules

>
>

Function Supporting Substring Variables

 
Changed:
<
<
Type Function Comment hfst-lexc hfst-twolc
OvertFstPair gr_construct (OvertFstHande e, OvertFstHande f) Combine two overt FSTs for generalized restriction operator.    
OvertFstPair gr_intersect (OvertFstPair gr1, OvertFstPair gr2) Combine two generalized restrictions under intersection.    
OvertFstPair gr_intersect_coherently (OvertFstPair gr1, OvertFstPair gr2) Combine two generalized restrictions under coherent intersection.    
OvertFstHandle gr_compile (OvertFstPair g, VarHandle x) Compiles
    generalized restriction φ =x> ψ or
    logical formula (∀ x)( φ(x) → ψ(x) )
where (φ,ψ)=g.
   
OvertFstHandle gr_compile_parallel (OvertFstPair g, VarSetHandle X) Compile
    generalized restriction φ =x1,...,xn> ψ or
    logical formula (∀ x1,...,xn)( φ(x1,...,xn) → ψ(x1,...,xn))
where (φ,ψ)=g and x1,...,xn ∈ X.
   
TransducerHandle gr_compile_final (OvertFstPair g) Compile
    generalized restriction φ =x1,...,xn> ψ or
    logical formula (∀ x1,...,xn)( φ(x1,...,xn) → ψ(x1,...,xn))
where (φ,ψ)=g.
   

Derived Functions

Functions That Compile Constraints using GR Rules

In the following, c is an overt FST for contexts.

Type Function Comment hfst-lexc hfst-twolc
OvertFstPair gr_construct_not (TransducerHandle t) not(t).    
OvertFstPair gr_construct_nowhere (TransducerHandle t) nowhere(t).    
OvertFstPair gr_construct_if_P_then_S (TransducerHandle p, TransducerHandle s) if-P-then-S(p,s) (Kaplan & Kay 1994).    
OvertFstPair gr_construct_if_S_then_P (TransducerHandle p, TransducerHandle s) if-S-then-P(p,s) (Kaplan & Kay 1994).    
OvertFstPair gr_construct_iff_P_S (TransducerHandle p, TransducerHandle s) iff-P-S(p,s) (Kaplan & Kay 1994).    
OvertFstPair gr_construct_center_prohibition (TransducerHandle x, OvertFstHandle c) center prohibition x /<= c (in TWOLC).    
OvertFstPair gr_construct_context_restriction (TransducerHandle x, OvertFstHandle c) context restriction x => c (Koskenniemi 1983).    
OvertFstPair gr_construct_coercion (TransducerHandle x, OvertFstHandle c) coercion x <<= c (Yli-Jyrä & Koskenniemi 2004).    
OvertFstPair gr_construct_output_coercion (TransducerHandle x, OvertFstHandle c) surface coercion x <= c (Koskenniemi 1983).    
OvertFstPair gr_construct_input_coercion (TransducerHandle x, OvertFstHandle c) lexical coercion x <- c (less used).    
OvertFstPair gr_construct_center_presence_requirement (TransducerHandle x, OvertFstHandle c) center presence requirement x <== c (Yli-Jyrä & Koskenniemi 2006).    
OvertFstPair gr_construct_presence_requirement (OvertFstHandle c1, OvertFstHandle c2) presence requirement c1 ==> c2 (Yli-Jyrä & Koskenniemi 2006).    
OvertFstPair gr_construct_output_double_arrow (TransducerHandle x, OvertFstHandle c) double arrow x <=> c (Koskenniemi 1983).    
OvertFstPair gr_construct_input_double_arrow (TransducerHandle x, OvertFstHandle c) double arrow x <-> c that combines a lexical coercion and a context restriction (less used).    
OvertFstPair gr_construct_match_L_R (TransducerHandle l, TransducerHandle d, TransducerHandle r) match-L-R(l,d,r) that says that a left side l (right side r) must always be paired with a right side r (left side l), and separated from that with a center that belongs to d (Yli-Jyrä 2007).    
OvertFstPair gr_construct_bracketing_restriction (TransducerHandle l, TransducerHandle r, TransducerHandle d, TransducerHandle c) bracketing restriction constraint # l __ R # => c according to which (∀ vxy)( v∈l ∧ x∈d ∧ y∈r → x∈d ) (Yli-Jyrä 2003).    

GR-Based Engines for Grammar Systems

The GR Calculus makes is easy to define some complete rule systems with rule application modes and conflict resolutions. The interfaces to the following systems will be added here:

  • Two-Level Grammars
  • Generalized Two-Level Grammars
  • Bracketed Generalized Two-Level Grammars
  • Parallel Replacement and Markup Rules
>
>
These functions are implemented in a latter stage. These are currently moved to HfstAPIGeneralizedRestrictionLayer2 in order to prioritize the work.
 

References

Revision 72008-10-13 - AnssiYliJyra

Line: 1 to 1
 
META TOPICPARENT name="HfstHome"

HFST: API for Generalized Restriction (GR) and Predicate Logic in FST Calculus

Added:
>
>

Introduction

Purpose of the layer

 This extension to the basic HFST API provides support for new letter-FST operations that are useful for compilation of
  • rewriting, replace and markup rules, constraint rules, contextual rules and grammars in general
  • Two-Level Phonology, Generative Phonology, Optimality Theoretic Phonology, and Autosegmental Phonology, and
  • lexicon formalisms and surface syntactic grammars.
Changed:
<
<
>
>

Prior references

 The current definitions are based on the convergence of two streams of work:
  • the Generalized Restriction framework (Yli-Jyrä & Koskenniemi 2004, 2006, 2007; Yli-Jyrä 2007a, 2007b)
  • the Regular Expressions and Predicate Logic (Hulden 2008).
The more general discussion on FST related arithmetics goes back to the work of Buchi (1960), Elgot (1961), etc. See Section References below.
Changed:
<
<
The basic and common notion in both streams is the notion of an auxiliary symbol that is used to indicate a boundary of a substring. This symbol has two names: a diamond and variable symbol (). More such symbols can be numbered or named according to letters using different notational conventions: 1, ◊2,..., <x>, <y>, ... (x), (y),..., x, y, .... These auxiliary symbols occur in strings of marker-augmented FSTs that we call below over FSTs (implemented through OvertFstHandle). The data type of an uncompiled generalized restriction is OvertFstPair.
>
>

Basic Notions

Auxiliary Marker Symbols

  1. The basic and common notion in both streams is the notion of an auxiliary symbol that is used to indicate a boundary of a substring. This symbol has two names: a diamond and variable symbol (). More such symbols can be numbered or named according to letters using different notational conventions: 1, ◊2,..., <x>, <y>, ... (x), (y),..., x, y, .... These auxiliary symbols occur in strings of marker-augmented FSTs that we call below over FSTs (interfaced through OvertFstHandle). The data type of an uncompiled generalized restriction is OvertFstPair.
  2. In addition to those e.g. dozen auxiliary symbols that have been employed by an application programmer, we need to prepare for hundreds of such auxiliary symbols that are created by special algorithms that speed up the compilation of the GR operation. These symbols are added in certain paths in order to make FSTs look simpler. Their number can be large since we want to more auxiliary symbols when we have a weighted GR operation in the future. For example, nondeterministic FST can be transformed to a deterministic one by adding such auxiliary symbols. Regardless of the purpose, the auxiliary symbols have the same type and it is interfaced through a VarHandle.
  3. There are many ways to use auxiliary markers. All these should be supported: (i) it occurs only once in every path of over FSTs, (ii) it occurs twice, (iii) it occurs 4 times, (iv) it occurs freely in specified positions. They can be removed one by one or once for all. Accordingly, auxiliary symbols are quite similar to normal symbols (or keys).
  4. Overt FSTs keep track of the known auxiliary markers that vary from FST to FST even if they could share the same key table. Those symbols that an FST does not know need to be added by harmonization when the FST is combined under intersection with other FSTs. There, loops for unknown auxiliaries are simply added.
  5. The complementation of over FST is computed w.r.t. the universal language over all pairs of known and unknown normal symbols and all the identity pairs of known auxiliary symbols.

Nondeterministic Letter Transducers

Often letter transducers are kept as deterministic and minimal. However, in the case of overt FSTs, we may want to avoid determinization of intermediate results.

Operations, Functions and Related Layers

  1. VarHandle can contain a KeyHandle rather than a SymbolHandle and it probably more feasible to implement that way.
  2. Excepting the harmonization and carrying the auxiliary symbol alphabet, most of the functionalities of this layer is based just normal FST operations provided by the TransducerLayer. Accordingly, the large number of operations in the current layer does not imply much programming.
  3. The functions in the current layer are all derived and their are mostly of similar complexity. We see all operations that use only overt FSTs as primitive while those build on over FST pairs are derived.
  4. However, the total set of possible pairs have to be defined somehow. Therefore, optional access to related =other=-symbol (or key) conventions would make the complementation more compact and efficient.
 

Data Types

Line: 24 to 42
 
OvertFstPair a pair of FSTs using variables    
TransducerHandle an HFST transducer without variable symbols    
Changed:
<
<

Definition of Substring Variables and other Diamond Symbols

>
>

Function Primitives

Definition of Substring Variables and other Diamond Symbols

 
Type Function Comment hfst-lexc hfst-twolc
Line: 36 to 55
 
VarHandle create_var_type3 () Create a FO variable denoting pairs of positions in each string (for marking a substring with sprinkled auxiliary symbols).    
-->
Changed:
<
<

Functions That Relate Substring Variables to Variable-Free Conditions

>
>

Functions That Relate Substring Variables to Variable-Free Conditions

 
Type Function Comment hfst-lexc hfst-twolc
Line: 48 to 67
 
OvertFstHandle var_follows (VarHandle x, TransducerHandle lc, bool padded) Asserts that substring x follows (padded) left context lc.    
(this table is subject to minor changes)
Changed:
<
<

Functions That Compare or Rename Substring Variables

>
>

Functions That Compare or Rename Substring Variables

 
Type Function Comment hfst-lexc hfst-twolc
Line: 64 to 83
 
OvertFstHandle var_is_suffix_of (VarHandle x, VarHandle y) Asserts that substring x is suffix of y.    
OvertFstHandle rename_var (VarHandle x, VarHandle y, OvertFstHandle ψ) Makes α transformation for overt FST ψ by replacing variable x with variable y.    
Changed:
<
<

Functions That Implement Logical Connectors and Quantifiers

>
>

Functions That Implement Logical Connectors and Quantifiers

 
Type Function Comment hfst-lexc hfst-twolc
Changed:
<
<
OvertFstHandle connect_with_and (OvertFstHande e, OvertFstHande f) Combined two overt FSTs under conjunction.    
OvertFstHandle connect_with_or (OvertFstHande e, OvertFstHande f) Combined two overt FSTs under disjunction.    
OvertFstHandle connect_with_xor (OvertFstHande e, OvertFstHande f) Combined two overt FSTs under exclusive disjunction.    
OvertFstHandle connect_with_not (OvertFstHande e) Negate overt FSTs.    
>
>
OvertFstHandle connect_with_concatenation (OvertFstHande e, OvertFstHande f) Combine two overt FSTs under contenation.    
OvertFstHandle connect_with_and (OvertFstHande e, OvertFstHande f) Combine two overt FSTs under conjunction.    
OvertFstHandle connect_with_or (OvertFstHande e, OvertFstHande f) Combine two overt FSTs under disjunction.    
OvertFstHandle connect_with_xor (OvertFstHande e, OvertFstHande f) Combine two overt FSTs under exclusive disjunction.    
OvertFstHandle connect_with_not (OvertFstHande e) Negate an overt FST.    
 
OvertFstHandle connect_with_arrow (OvertFstHande e, OvertFstHande f) Combine two overt FSTs with material implication.    
OvertFstHandle quantify_existentially (VarHandle m, OvertFstHandle φ) Hides diamond x in φ,
or computes (∃ x)φ(x).
   
OvertFstHandle quantify_universally (VarHandle m, OvertFstHandle φ) Restrict x to all substrings in φ by evaluating
    Σ* <x> Σ* <x> Σ*  =x>  φ
or computes (∀ x)φ(x).
   
Changed:
<
<

Functions That Construct, Combine and Compile GR Rules

>
>

Functions That Construct, Combine and Compile GR Rules

 
Type Function Comment hfst-lexc hfst-twolc
Line: 87 to 107
 
OvertFstHandle gr_compile_parallel (OvertFstPair g, VarSetHandle X) Compile
    generalized restriction φ =x1,...,xn> ψ or
    logical formula (∀ x1,...,xn)( φ(x1,...,xn) → ψ(x1,...,xn))
where (φ,ψ)=g and x1,...,xn ∈ X.
   
TransducerHandle gr_compile_final (OvertFstPair g) Compile
    generalized restriction φ =x1,...,xn> ψ or
    logical formula (∀ x1,...,xn)( φ(x1,...,xn) → ψ(x1,...,xn))
where (φ,ψ)=g.
   
Changed:
<
<

Functions That Compile Constraints using GR Rules

>
>

Derived Functions

Functions That Compile Constraints using GR Rules

  In the following, c is an overt FST for contexts.
Line: 110 to 132
 
OvertFstPair gr_construct_match_L_R (TransducerHandle l, TransducerHandle d, TransducerHandle r) match-L-R(l,d,r) that says that a left side l (right side r) must always be paired with a right side r (left side l), and separated from that with a center that belongs to d (Yli-Jyrä 2007).    
OvertFstPair gr_construct_bracketing_restriction (TransducerHandle l, TransducerHandle r, TransducerHandle d, TransducerHandle c) bracketing restriction constraint # l __ R # => c according to which (∀ vxy)( v∈l ∧ x∈d ∧ y∈r → x∈d ) (Yli-Jyrä 2003).    
Changed:
<
<

GR-Based Engines for Grammar Systems

>
>

GR-Based Engines for Grammar Systems

  The GR Calculus makes is easy to define some complete rule systems with rule application modes and conflict resolutions. The interfaces to the following systems will be added here:
  • Two-Level Grammars

Revision 62008-10-13 - AnssiYliJyra

Line: 1 to 1
 
META TOPICPARENT name="HfstHome"

HFST: API for Generalized Restriction (GR) and Predicate Logic in FST Calculus

Line: 12 to 12
 
  • the Regular Expressions and Predicate Logic (Hulden 2008).
The more general discussion on FST related arithmetics goes back to the work of Buchi (1960), Elgot (1961), etc. See Section References below.
Changed:
<
<
The basic and common notion in both streams is the notion of an auxiliary symbol that is used to indicate a boundary of a substring. This symbol has two names: a diamond and variable symbol (). More such symbols can be numbered or named according to letters using different notational conventions: 1, ◊2,..., <x>, <y>, ... (x), (y),..., x, y, .... These auxiliary symbols occur in strings of FSTs that are referred by LamdaFstHandles.
>
>
The basic and common notion in both streams is the notion of an auxiliary symbol that is used to indicate a boundary of a substring. This symbol has two names: a diamond and variable symbol (). More such symbols can be numbered or named according to letters using different notational conventions: 1, ◊2,..., <x>, <y>, ... (x), (y),..., x, y, .... These auxiliary symbols occur in strings of marker-augmented FSTs that we call below over FSTs (implemented through OvertFstHandle). The data type of an uncompiled generalized restriction is OvertFstPair.
 

Data Types

Line: 20 to 20
 
Type Comment hfst-lexc hfst-twolc
VarHandle a variable denoting positions in strings and used in different ways according to the variable type (on boundaries, sprinkled, members)    
VarSetHandle a set of variables    
Changed:
<
<
LambdaFstHandle an FST using variables that are not yet bound to any value    
LambdaFstPair a pair of FSTs using variables    
>
>
OvertFstHandle an FST using variables that are not yet bound to any value    
OvertFstPair a pair of FSTs using variables    
 
TransducerHandle an HFST transducer without variable symbols    

Definition of Substring Variables and other Diamond Symbols

Line: 40 to 40
 
Type Function Comment hfst-lexc hfst-twolc
Changed:
<
<
LambdaFstHandle var_is_member (VarHandle x, TransducerHandle t) Asserts that substring x is recognized by t.    
LambdaFstHandle var_partition (VarHandle v, VarHandle x, VarHandle y) Asserts that string is partitioned into substrings v, x and y.    
LambdaFstHandle var_is_substring_with_context (VarHandle x, TransducerHandle rc, TransducerHandle cntr, TransducerHandle rc, bool padded) Asserts that x is substring of strings in cntr that is surrounded by (padded) contexts lc and rc.    
LambdaFstHandle var_has_context (VarHandle x, TransducerHandle lc, TransducerHandle rc, bool padded) Asserts that substring x is surrounded by (padded) contexts lc and rc.    
LambdaFstHandle var_precedes (VarHandle x, TransducerHandle rc, bool padded) Asserts that substring x precedes (padded) right context rc.    
LambdaFstHandle var_follows (VarHandle x, TransducerHandle lc, bool padded) Asserts that substring x follows (padded) left context lc.    
>
>
OvertFstHandle var_is_member (VarHandle x, TransducerHandle t) Asserts that substring x is recognized by t.    
OvertFstHandle var_partition (VarHandle v, VarHandle x, VarHandle y) Asserts that string is partitioned into substrings v, x and y.    
OvertFstHandle var_is_substring_with_context (VarHandle x, TransducerHandle rc, TransducerHandle cntr, TransducerHandle rc, bool padded) Asserts that x is substring of strings in cntr that is surrounded by (padded) contexts lc and rc.    
OvertFstHandle var_has_context (VarHandle x, TransducerHandle lc, TransducerHandle rc, bool padded) Asserts that substring x is surrounded by (padded) contexts lc and rc.    
OvertFstHandle var_precedes (VarHandle x, TransducerHandle rc, bool padded) Asserts that substring x precedes (padded) right context rc.    
OvertFstHandle var_follows (VarHandle x, TransducerHandle lc, bool padded) Asserts that substring x follows (padded) left context lc.    
 (this table is subject to minor changes)

Functions That Compare or Rename Substring Variables

Type Function Comment hfst-lexc hfst-twolc
Changed:
<
<
LambdaFstHandle var_embeds (VarHandle x, VarHandle y) Asserts that substring x contains substring y.    
LambdaFstHandle var_equals (VarHandle x, VarHandle y) Asserts that substrings x and y are equal.    
LambdaFstHandle var_starts_simultaneously (VarHandle x, VarHandle y) Asserts that substrings x and y are equal.    
LambdaFstHandle var_ends_simultaneously (VarHandle x, VarHandle y) Asserts that substrings x and y are equal.    
LambdaFstHandle var_starts_before (VarHandle x, VarHandle y) Asserts that substring x starts before substring y.    
LambdaFstHandle var_ends_before (VarHandle x, VarHandle y) Asserts that substring x ends before substring y.    
LambdaFstHandle var_comes_before (VarHandle x, VarHandle y) Asserts that substring x occurs ends before substring y starts.    
LambdaFstHandle var_has_overlap (VarHandle x, VarHandle y) Asserts that substring x and substring y are not disjoint (Hulden 2008).    
LambdaFstHandle var_is_prefix_of (VarHandle x, VarHandle y) Asserts that substring x is prefix of y.    
LambdaFstHandle var_is_suffix_of (VarHandle x, VarHandle y) Asserts that substring x is suffix of y.    
LambdaFstHandle rename_var (VarHandle x, VarHandle y, LambdaFstHandle ψ) Makes α transformation for lambda FST ψ by replacing variable x with variable y.    
>
>
OvertFstHandle var_embeds (VarHandle x, VarHandle y) Asserts that substring x contains substring y.    
OvertFstHandle var_equals (VarHandle x, VarHandle y) Asserts that substrings x and y are equal.    
OvertFstHandle var_starts_simultaneously (VarHandle x, VarHandle y) Asserts that substrings x and y are equal.    
OverFstHandle var_ends_simultaneously (VarHandle x, VarHandle y) Asserts that substrings x and y are equal.    
OvertFstHandle var_starts_before (VarHandle x, VarHandle y) Asserts that substring x starts before substring y.    
OvertFstHandle var_ends_before (VarHandle x, VarHandle y) Asserts that substring x ends before substring y.    
OvertFstHandle var_comes_before (VarHandle x, VarHandle y) Asserts that substring x occurs ends before substring y starts.    
OvertFstHandle var_has_overlap (VarHandle x, VarHandle y) Asserts that substring x and substring y are not disjoint (Hulden 2008).    
OvertFstHandle var_is_prefix_of (VarHandle x, VarHandle y) Asserts that substring x is prefix of y.    
OvertFstHandle var_is_suffix_of (VarHandle x, VarHandle y) Asserts that substring x is suffix of y.    
OvertFstHandle rename_var (VarHandle x, VarHandle y, OvertFstHandle ψ) Makes α transformation for overt FST ψ by replacing variable x with variable y.    
 

Functions That Implement Logical Connectors and Quantifiers

Type Function Comment hfst-lexc hfst-twolc
Changed:
<
<
LambdaFstHandle connect_with_and (LambdaFstHande e, LambdaFstHande f) Combined two lambda FSTs under conjunction.    
LambdaFstHandle connect_with_or (LambdaFstHande e, LambdaFstHande f) Combined two lambda FSTs under disjunction.    
LambdaFstHandle connect_with_xor (LambdaFstHande e, LambdaFstHande f) Combined two lambda FSTs under exclusive disjunction.    
LambdaFstHandle connect_with_not (LambdaFstHande e) Negate lambda FSTs.    
LambdaFstHandle connect_with_arrow (LambdaFstHande e, LambdaFstHande f) Combine two lambda FSTs with material implication.    
LambdaFstHandle quantify_existentially (VarHandle m, LambdaFstHandle φ) Hides diamond x in φ,
or computes (∃ x)φ(x).
   
LambdaFstHandle quantify_universally (VarHandle m, LambdaFstHandle φ) Restrict x to all substrings in φ by evaluating
    Σ* <x> Σ* <x> Σ*  =x>  φ
or computes (∀ x)φ(x).
   
>
>
OvertFstHandle connect_with_and (OvertFstHande e, OvertFstHande f) Combined two overt FSTs under conjunction.    
OvertFstHandle connect_with_or (OvertFstHande e, OvertFstHande f) Combined two overt FSTs under disjunction.    
OvertFstHandle connect_with_xor (OvertFstHande e, OvertFstHande f) Combined two overt FSTs under exclusive disjunction.    
OvertFstHandle connect_with_not (OvertFstHande e) Negate overt FSTs.    
OvertFstHandle connect_with_arrow (OvertFstHande e, OvertFstHande f) Combine two overt FSTs with material implication.    
OvertFstHandle quantify_existentially (VarHandle m, OvertFstHandle φ) Hides diamond x in φ,
or computes (∃ x)φ(x).
   
OvertFstHandle quantify_universally (VarHandle m, OvertFstHandle φ) Restrict x to all substrings in φ by evaluating
    Σ* <x> Σ* <x> Σ*  =x>  φ
or computes (∀ x)φ(x).
   
 

Functions That Construct, Combine and Compile GR Rules

Type Function Comment hfst-lexc hfst-twolc
Changed:
<
<
LambdaFstPair gr_construct (LambdaFstHande e, LambdaFstHande f) Combine two lambda FSTs for generalized restriction operator.    
LambdaFstPair gr_intersect (LambdaFstPair gr1, LambdaFstPair gr2) Combine two generalized restrictions under intersection.    
LambdaFstPair gr_intersect_coherently (LambdaFstPair gr1, LambdaFstPair gr2) Combine two generalized restrictions under coherent intersection.    
LambdaFstHandle gr_compile (LambdaFstPair g, VarHandle x) Compiles
    generalized restriction φ =x> ψ or
    logical formula (∀ x)( φ(x) → ψ(x) )
where (φ,ψ)=g.
   
LambdaFstHandle gr_compile_parallel (LambdaFstPair g, VarSetHandle X) Compile
    generalized restriction φ =x1,...,xn> ψ or
    logical formula (∀ x1,...,xn)( φ(x1,...,xn) → ψ(x1,...,xn))
where (φ,ψ)=g and x1,...,xn ∈ X.
   
TransducerHandle gr_compile_final (LambdaFstPair g) Compile
    generalized restriction φ =x1,...,xn> ψ or
    logical formula (∀ x1,...,xn)( φ(x1,...,xn) → ψ(x1,...,xn))
where (φ,ψ)=g.
   
>
>
OvertFstPair gr_construct (OvertFstHande e, OvertFstHande f) Combine two overt FSTs for generalized restriction operator.    
OvertFstPair gr_intersect (OvertFstPair gr1, OvertFstPair gr2) Combine two generalized restrictions under intersection.    
OvertFstPair gr_intersect_coherently (OvertFstPair gr1, OvertFstPair gr2) Combine two generalized restrictions under coherent intersection.    
OvertFstHandle gr_compile (OvertFstPair g, VarHandle x) Compiles
    generalized restriction φ =x> ψ or
    logical formula (∀ x)( φ(x) → ψ(x) )
where (φ,ψ)=g.
   
OvertFstHandle gr_compile_parallel (OvertFstPair g, VarSetHandle X) Compile
    generalized restriction φ =x1,...,xn> ψ or
    logical formula (∀ x1,...,xn)( φ(x1,...,xn) → ψ(x1,...,xn))
where (φ,ψ)=g and x1,...,xn ∈ X.
   
TransducerHandle gr_compile_final (OvertFstPair g) Compile
    generalized restriction φ =x1,...,xn> ψ or
    logical formula (∀ x1,...,xn)( φ(x1,...,xn) → ψ(x1,...,xn))
where (φ,ψ)=g.
   
 

Functions That Compile Constraints using GR Rules

Changed:
<
<
In the following, c is a lambda FST for contexts.
>
>
In the following, c is an overt FST for contexts.
 
Type Function Comment hfst-lexc hfst-twolc
Changed:
<
<
LambdaFstPair gr_construct_not (TransducerHandle t) not(t).    
LambdaFstPair gr_construct_nowhere (TransducerHandle t) nowhere(t).    
LambdaFstPair gr_construct_if_P_then_S (TransducerHandle p, TransducerHandle s) if-P-then-S(p,s) (Kaplan & Kay 1994).    
LambdaFstPair gr_construct_if_S_then_P (TransducerHandle p, TransducerHandle s) if-S-then-P(p,s) (Kaplan & Kay 1994).    
LambdaFstPair gr_construct_iff_P_S (TransducerHandle p, TransducerHandle s) iff-P-S(p,s) (Kaplan & Kay 1994).    
LambdaFstPair gr_construct_center_prohibition (TransducerHandle x, LambdaFstHandle c) center prohibition x /<= c (in TWOLC).    
LambdaFstPair gr_construct_context_restriction (TransducerHandle x, LambdaFstHandle c) context restriction x => c (Koskenniemi 1983).    
LambdaFstPair gr_construct_coercion (TransducerHandle x, LambdaFstHandle c) coercion x <<= c (Yli-Jyrä & Koskenniemi 2004).    
LambdaFstPair gr_construct_output_coercion (TransducerHandle x, LambdaFstHandle c) surface coercion x <= c (Koskenniemi 1983).    
LambdaFstPair gr_construct_input_coercion (TransducerHandle x, LambdaFstHandle c) lexical coercion x <- c (less used).    
LambdaFstPair gr_construct_center_presence_requirement (TransducerHandle x, LambdaFstHandle c) center presence requirement x <== c (Yli-Jyrä & Koskenniemi 2006).    
LambdaFstPair gr_construct_presence_requirement (LambdaFstHandle c1, LambdaFstHandle c2) presence requirement c1 ==> c2 (Yli-Jyrä & Koskenniemi 2006).    
LambdaFstPair gr_construct_output_double_arrow (TransducerHandle x, LambdaFstHandle c) double arrow x <=> c (Koskenniemi 1983).    
LambdaFstPair gr_construct_input_double_arrow (TransducerHandle x, LambdaFstHandle c) double arrow x <-> c that combines a lexical coercion and a context restriction (less used).    
LambdaFstPair gr_construct_match_L_R (TransducerHandle l, TransducerHandle d, TransducerHandle r) match-L-R(l,d,r) that says that a left side l (right side r) must always be paired with a right side r (left side l), and separated from that with a center that belongs to d (Yli-Jyrä 2007).    
LambdaFstPair gr_construct_bracketing_restriction (TransducerHandle l, TransducerHandle r, TransducerHandle d, TransducerHandle c) bracketing restriction constraint # l __ R # => c according to which (∀ vxy)( v∈l ∧ x∈d ∧ y∈r → x∈d ) (Yli-Jyrä 2003).    
>
>
OvertFstPair gr_construct_not (TransducerHandle t) not(t).    
OvertFstPair gr_construct_nowhere (TransducerHandle t) nowhere(t).    
OvertFstPair gr_construct_if_P_then_S (TransducerHandle p, TransducerHandle s) if-P-then-S(p,s) (Kaplan & Kay 1994).    
OvertFstPair gr_construct_if_S_then_P (TransducerHandle p, TransducerHandle s) if-S-then-P(p,s) (Kaplan & Kay 1994).    
OvertFstPair gr_construct_iff_P_S (TransducerHandle p, TransducerHandle s) iff-P-S(p,s) (Kaplan & Kay 1994).    
OvertFstPair gr_construct_center_prohibition (TransducerHandle x, OvertFstHandle c) center prohibition x /<= c (in TWOLC).    
OvertFstPair gr_construct_context_restriction (TransducerHandle x, OvertFstHandle c) context restriction x => c (Koskenniemi 1983).    
OvertFstPair gr_construct_coercion (TransducerHandle x, OvertFstHandle c) coercion x <<= c (Yli-Jyrä & Koskenniemi 2004).    
OvertFstPair gr_construct_output_coercion (TransducerHandle x, OvertFstHandle c) surface coercion x <= c (Koskenniemi 1983).    
OvertFstPair gr_construct_input_coercion (TransducerHandle x, OvertFstHandle c) lexical coercion x <- c (less used).    
OvertFstPair gr_construct_center_presence_requirement (TransducerHandle x, OvertFstHandle c) center presence requirement x <== c (Yli-Jyrä & Koskenniemi 2006).    
OvertFstPair gr_construct_presence_requirement (OvertFstHandle c1, OvertFstHandle c2) presence requirement c1 ==> c2 (Yli-Jyrä & Koskenniemi 2006).    
OvertFstPair gr_construct_output_double_arrow (TransducerHandle x, OvertFstHandle c) double arrow x <=> c (Koskenniemi 1983).    
OvertFstPair gr_construct_input_double_arrow (TransducerHandle x, OvertFstHandle c) double arrow x <-> c that combines a lexical coercion and a context restriction (less used).    
OvertFstPair gr_construct_match_L_R (TransducerHandle l, TransducerHandle d, TransducerHandle r) match-L-R(l,d,r) that says that a left side l (right side r) must always be paired with a right side r (left side l), and separated from that with a center that belongs to d (Yli-Jyrä 2007).    
OvertFstPair gr_construct_bracketing_restriction (TransducerHandle l, TransducerHandle r, TransducerHandle d, TransducerHandle c) bracketing restriction constraint # l __ R # => c according to which (∀ vxy)( v∈l ∧ x∈d ∧ y∈r → x∈d ) (Yli-Jyrä 2003).    
 

GR-Based Engines for Grammar Systems

Revision 52008-10-08 - AnssiYliJyra

Line: 1 to 1
 
META TOPICPARENT name="HfstHome"

HFST: API for Generalized Restriction (GR) and Predicate Logic in FST Calculus

Line: 12 to 12
 
  • the Regular Expressions and Predicate Logic (Hulden 2008).
The more general discussion on FST related arithmetics goes back to the work of Buchi (1960), Elgot (1961), etc. See Section References below.
Changed:
<
<
The basic and common notion in both streams is the notion of an auxiliary symbol that is used to indicate a boundary of a substring. This symbol has two names: a diamond and variable symbol (). More such symbols can be numbered or named according to letters using different notational conventions: 1, ◊2,..., <x>, <y>, ... (x), (y),..., x, y, .... These auxiliary symbols occur in strings of FSTs that are referred by LamdaExpHandles.
>
>
The basic and common notion in both streams is the notion of an auxiliary symbol that is used to indicate a boundary of a substring. This symbol has two names: a diamond and variable symbol (). More such symbols can be numbered or named according to letters using different notational conventions: 1, ◊2,..., <x>, <y>, ... (x), (y),..., x, y, .... These auxiliary symbols occur in strings of FSTs that are referred by LamdaFstHandles.
 

Data Types

Revision 42008-10-07 - AnssiYliJyra

Line: 1 to 1
 
META TOPICPARENT name="HfstHome"

HFST: API for Generalized Restriction (GR) and Predicate Logic in FST Calculus

Line: 10 to 10
 The current definitions are based on the convergence of two streams of work:
  • the Generalized Restriction framework (Yli-Jyrä & Koskenniemi 2004, 2006, 2007; Yli-Jyrä 2007a, 2007b)
  • the Regular Expressions and Predicate Logic (Hulden 2008).
Changed:
<
<
The more general background goes to the work of Buchi (1960), Elgot (1961), etc. See Section References below.
>
>
The more general discussion on FST related arithmetics goes back to the work of Buchi (1960), Elgot (1961), etc. See Section References below.
  The basic and common notion in both streams is the notion of an auxiliary symbol that is used to indicate a boundary of a substring. This symbol has two names: a diamond and variable symbol (). More such symbols can be numbered or named according to letters using different notational conventions: 1, ◊2,..., <x>, <y>, ... (x), (y),..., x, y, .... These auxiliary symbols occur in strings of FSTs that are referred by LamdaExpHandles.
Line: 42 to 42
 
Type Function Comment hfst-lexc hfst-twolc
LambdaFstHandle var_is_member (VarHandle x, TransducerHandle t) Asserts that substring x is recognized by t.    
LambdaFstHandle var_partition (VarHandle v, VarHandle x, VarHandle y) Asserts that string is partitioned into substrings v, x and y.    
Changed:
<
<
LambdaFstHandle var_has_context (VarHandle x, TransducerHandle rc, TransducerHandle rc, bool padded) Asserts that substring x is surrounded by (padded) contexts lc and rc.    
>
>
LambdaFstHandle var_is_substring_with_context (VarHandle x, TransducerHandle rc, TransducerHandle cntr, TransducerHandle rc, bool padded) Asserts that x is substring of strings in cntr that is surrounded by (padded) contexts lc and rc.    
LambdaFstHandle var_has_context (VarHandle x, TransducerHandle lc, TransducerHandle rc, bool padded) Asserts that substring x is surrounded by (padded) contexts lc and rc.    
 
LambdaFstHandle var_precedes (VarHandle x, TransducerHandle rc, bool padded) Asserts that substring x precedes (padded) right context rc.    
LambdaFstHandle var_follows (VarHandle x, TransducerHandle lc, bool padded) Asserts that substring x follows (padded) left context lc.    
Added:
>
>
(this table is subject to minor changes)
 

Functions That Compare or Rename Substring Variables

Line: 99 to 101
 
LambdaFstPair gr_construct_center_prohibition (TransducerHandle x, LambdaFstHandle c) center prohibition x /<= c (in TWOLC).    
LambdaFstPair gr_construct_context_restriction (TransducerHandle x, LambdaFstHandle c) context restriction x => c (Koskenniemi 1983).    
LambdaFstPair gr_construct_coercion (TransducerHandle x, LambdaFstHandle c) coercion x <<= c (Yli-Jyrä & Koskenniemi 2004).    
Changed:
<
<
LambdaFstPair gr_construct_input_coercion (TransducerHandle x, LambdaFstHandle c) surface coercion x <= c (Koskenniemi 1983).    
LambdaFstPair gr_construct_output_coercion (TransducerHandle x, LambdaFstHandle c) lexical coercion x <- c (less used).    
>
>
LambdaFstPair gr_construct_output_coercion (TransducerHandle x, LambdaFstHandle c) surface coercion x <= c (Koskenniemi 1983).    
LambdaFstPair gr_construct_input_coercion (TransducerHandle x, LambdaFstHandle c) lexical coercion x <- c (less used).    
 
LambdaFstPair gr_construct_center_presence_requirement (TransducerHandle x, LambdaFstHandle c) center presence requirement x <== c (Yli-Jyrä & Koskenniemi 2006).    
LambdaFstPair gr_construct_presence_requirement (LambdaFstHandle c1, LambdaFstHandle c2) presence requirement c1 ==> c2 (Yli-Jyrä & Koskenniemi 2006).    
Changed:
<
<
LambdaFstPair gr_construct_input_double_arrow (TransducerHandle x, LambdaFstHandle c) double arrow x <=> c (Koskenniemi 1983).    
LambdaFstPair gr_construct_output_double_arrow (TransducerHandle x, LambdaFstHandle c) double arrow x <-> c that combines a lexical coercion and a context restriction (less used).    
>
>
LambdaFstPair gr_construct_output_double_arrow (TransducerHandle x, LambdaFstHandle c) double arrow x <=> c (Koskenniemi 1983).    
LambdaFstPair gr_construct_input_double_arrow (TransducerHandle x, LambdaFstHandle c) double arrow x <-> c that combines a lexical coercion and a context restriction (less used).    
 
LambdaFstPair gr_construct_match_L_R (TransducerHandle l, TransducerHandle d, TransducerHandle r) match-L-R(l,d,r) that says that a left side l (right side r) must always be paired with a right side r (left side l), and separated from that with a center that belongs to d (Yli-Jyrä 2007).    
LambdaFstPair gr_construct_bracketing_restriction (TransducerHandle l, TransducerHandle r, TransducerHandle d, TransducerHandle c) bracketing restriction constraint # l __ R # => c according to which (∀ vxy)( v∈l ∧ x∈d ∧ y∈r → x∈d ) (Yli-Jyrä 2003).    
Changed:
<
<

References

>
>

GR-Based Engines for Grammar Systems

The GR Calculus makes is easy to define some complete rule systems with rule application modes and conflict resolutions. The interfaces to the following systems will be added here:

  • Two-Level Grammars
  • Generalized Two-Level Grammars
  • Bracketed Generalized Two-Level Grammars
  • Parallel Replacement and Markup Rules
 
Changed:
<
<
(to be added)
>
>

References

 
Added:
>
>
  • C. Elgot: Decision problems of finite automata and related arithmetics. Trans. Amer. Math. Soc. 98: 21-51 (1961)
  • R. Cohen and J. Brzozowski: Dot-depth of star-free events. J. Comput. Syst. Sci. 5:1-16 (1971)
  • W. Thomas: Classifying Regular Events in Symbolic Logic. J. C. S. Sci. 25(3): 360-376 (1982)
  • N. Vaillette: Logical specification of regular relations for NLP. Natural Language Engineering 9(1): 65-85. (2003)
  • A. Yli-Jyrä: Describing syntax with star-free expressions. In EACL 2003. 379-386. (2003)
  • --: Contributions to the Theory of Finite-State Based Grammars. Dissertation. (2005a)
  • --: Linguistic Grammars with Very Low Complexity. In Arppe et al., Inquiries into Words, Constraints and Contexts. CSLI Publications. (2005b)
  • --: Applications of Diamonded Double Negation. Invited talk (original title: Hidden Jewels of Double Negation). FSMNLP 2007 postproceedings. (2007a)
  • --: Transducers from Parallel Replace Rules and Modes with Generalized Lenient Composition. FSMNLP 2007 postproceedings. (2007b)
  • -- and K. Koskenniemi: Compiling contextual restrictions on strings into finite-state automata. FASTAR Days. Eindhoven. (2004)
  • -- and --: Compiling Generalized Two-Level Rules and Grammars. FinTAL 2006: 174-185. (2006)
  • -- and --: A New Method for Compiling Parallel Replacement Rules. CIAA 2007: 320-321 (2007c)
  • M. Hulden. Regular expressions and predicate logic in finite-state language processing. FSMNLP 2008. (2008)
 

Revision 32008-10-06 - AnssiYliJyra

Line: 1 to 1
 
META TOPICPARENT name="HfstHome"

HFST: API for Generalized Restriction (GR) and Predicate Logic in FST Calculus

Line: 12 to 12
 
  • the Regular Expressions and Predicate Logic (Hulden 2008).
The more general background goes to the work of Buchi (1960), Elgot (1961), etc. See Section References below.
Changed:
<
<
The basic and common notion in both streams is the notion of an auxiliary symbol that is used to indicate a boundary of a substring. This symbol has two names: a diamond <> and variable symbol (). More such symbols can be numbered or named according to letters: <>1, <>2,..., <x>, <y>, ... (x), (y),.... These auxiliary symbols occur in strings of FSTs that are referred by LamdaExpHandles.
>
>
The basic and common notion in both streams is the notion of an auxiliary symbol that is used to indicate a boundary of a substring. This symbol has two names: a diamond and variable symbol (). More such symbols can be numbered or named according to letters using different notational conventions: 1, ◊2,..., <x>, <y>, ... (x), (y),..., x, y, .... These auxiliary symbols occur in strings of FSTs that are referred by LamdaExpHandles.

Data Types

Type Comment hfst-lexc hfst-twolc
VarHandle a variable denoting positions in strings and used in different ways according to the variable type (on boundaries, sprinkled, members)    
VarSetHandle a set of variables    
LambdaFstHandle an FST using variables that are not yet bound to any value    
LambdaFstPair a pair of FSTs using variables    
TransducerHandle an HFST transducer without variable symbols    
 

Definition of Substring Variables and other Diamond Symbols

Type Function Comment hfst-lexc hfst-twolc
Changed:
<
<
VarHandle create_var_type2 () Create a FO variable denoting pairs of positions in each string    
>
>
VarHandle create_var_type2 () Create a FO variable used for boundaries of a substring    
VarSetHandle create_var_set () Create an empty set of FO variables    
VarSetHandle insert_var (VarSetHandle s, VarHandle x) Insert an FO variable to set s    
 

Revision 22008-10-06 - AnssiYliJyra

Line: 1 to 1
 
META TOPICPARENT name="HfstHome"

HFST: API for Generalized Restriction (GR) and Predicate Logic in FST Calculus

Added:
>
>
This extension to the basic HFST API provides support for new letter-FST operations that are useful for compilation of
  • rewriting, replace and markup rules, constraint rules, contextual rules and grammars in general
  • Two-Level Phonology, Generative Phonology, Optimality Theoretic Phonology, and Autosegmental Phonology, and
  • lexicon formalisms and surface syntactic grammars.

The current definitions are based on the convergence of two streams of work:

  • the Generalized Restriction framework (Yli-Jyrä & Koskenniemi 2004, 2006, 2007; Yli-Jyrä 2007a, 2007b)
  • the Regular Expressions and Predicate Logic (Hulden 2008).
The more general background goes to the work of Buchi (1960), Elgot (1961), etc. See Section References below.

The basic and common notion in both streams is the notion of an auxiliary symbol that is used to indicate a boundary of a substring. This symbol has two names: a diamond <> and variable symbol (). More such symbols can be numbered or named according to letters: <>1, <>2,..., <x>, <y>, ... (x), (y),.... These auxiliary symbols occur in strings of FSTs that are referred by LamdaExpHandles.

Definition of Substring Variables and other Diamond Symbols

 
Type Function Comment hfst-lexc hfst-twolc
VarHandle create_var_type2 () Create a FO variable denoting pairs of positions in each string    
Added:
>
>

Functions That Relate Substring Variables to Variable-Free Conditions

 
Type Function Comment hfst-lexc hfst-twolc
Changed:
<
<
LambdaExpHandle var_ismember (VarHandle x, TransducerHandle t) Asserts that sequence x is recognized by t.    
LambdaExpHandle var_has_context (VarHandle x, TransducerHandle rc, TransducerHandle rc, bool padded) Asserts that sequence x is surrounded by (padded) contexts lc and rc.    
>
>
LambdaExpHandle var_ismember (VarHandle x, TransducerHandle t) Asserts that substring x is recognized by t.    
LambdaExpHandle var_has_context (VarHandle x, TransducerHandle rc, TransducerHandle rc, bool padded) Asserts that substring x is surrounded by (padded) contexts lc and rc.    
 
LambdaExpHandle var_precedes (VarHandle x, TransducerHandle rc, bool padded) Asserts that substring x precedes (padded) right context rc.    
LambdaExpHandle var_follows (VarHandle x, TransducerHandle lc, bool padded) Asserts that substring x follows (padded) left context lc.    
Changed:
<
<
LambdaExpHandle var_rename (VarHandle x, VarHandle y, LambdaExpHandle ψ) Makes α transformation for lambda expression ψ by replacing variable x with variable y.    
LambdaExpHandle var_interpret_gr (VarHandle m, LambdaExpHandle φ, LambdaExpHandle ψ) Compiles
    generalized restriction φ(x) =m> ψ(x)
or
    logical expression (∀ x)( φ(x) → ψ(x) )
into an FST without variable x. The universal letter FST is assumed to defined over all letter pairs and variable symbols.
   
TransducerHandle var_interpret_gr (LambdaExpHandle φ, LambdaExpHandle ψ) Compiles
    generalized restriction φ(x1,...,xn) =m> ψ(x1,...,xn)
or
    logical expression (∀ x1,...,xn)( φ(x1,...,xn) → ψ(x1,...,xn) )
into a letter FST. The universal letter FST is assumed to defined over all letter pairs.
   
>
>

Functions That Implement Logical Connectors

Type Function Comment hfst-lexc hfst-twolc
LambdaExpHandle var_connect_with_and (LambdaExpHande e, LambdaExpHande f) Combined two lambda expressions under conjunction.    
LambdaExpHandle var_connect_with_or (LambdaExpHande e, LambdaExpHande f) Combined two lambda expressions under disjunction.    
LambdaExpHandle var_connect_with_xor (LambdaExpHande e, LambdaExpHande f) Combined two lambda expressions under exclusive disjunction.    
LambdaExpHandle var_connect_with_not (LambdaExpHande e) Negate lambda expressions.    
LambdaExpHandle var_connect_with_arrow (LambdaExpHande e, LambdaExpHande f) Combe two lambda expressions with material implication.    

Functions That Compare or Rename Substring Variables

Type Function Comment hfst-lexc hfst-twolc
LambdaExpHandle var_embeds (VarHandle x, VarHandle y) Asserts that substring x contains substring y.    
LambdaExpHandle var_equals (VarHandle x, VarHandle y) Asserts that substrings x and y are equal.    
LambdaExpHandle var_starts_simultaneously (VarHandle x, VarHandle y) Asserts that substrings x and y are equal.    
LambdaExpHandle var_ends_simultaneously (VarHandle x, VarHandle y) Asserts that substrings x and y are equal.    
LambdaExpHandle var_starts_before (VarHandle x, VarHandle y) Asserts that substring x starts before substring y.    
LambdaExpHandle var_ends_before (VarHandle x, VarHandle y) Asserts that substring x ends before substring y.    
LambdaExpHandle var_comes_before (VarHandle x, VarHandle y) Asserts that substring x occurs ends before substring y starts.    
LambdaExpHandle var_has_overlap (VarHandle x, VarHandle y) Asserts that substring x and substring y are not disjoint.    
LambdaExpHandle var_is_prefix_of (VarHandle x, VarHandle y) Asserts that substring x is prefix of y.    
LambdaExpHandle var_is_suffix_of (VarHandle x, VarHandle y) Asserts that substring x is suffix of y.    
LambdaExpHandle var_renames (VarHandle x, VarHandle y, LambdaExpHandle ψ) Makes α transformation for lambda expression ψ by replacing variable x with variable y.    

Functions That Implement Quatification of Variables

LambdaExpHandle quantify_existentially (VarHandle m, LambdaExpHandle φ) Hides diamond x in φ, or
quantifies variable x existentially in lambda expression φ.
   
LambdaExpHandle quantify_universally (VarHandle m, LambdaExpHandle φ) Restrict x to all substrings in φ by evaluating
    Σ* <x> Σ* <x> Σ*  =x>  φ(x)
or quantifies variable x universally in lambda expression φ.
   
LambdaExpHandle var_compile_gr (VarHandle m, LambdaExpHandle φ, LambdaExpHandle ψ) Compiles
    generalized restriction φ =x> ψ
or
    logical formula (∀ x)( φ(x) → ψ(x) )
into an FST without variable x. The universal letter FST is assumed to defined over all letter pairs and variable symbols.
   
TransducerHandle var_compile_gr (LambdaExpHandle φ, LambdaExpHandle ψ) Compiles
    generalized restriction φ =x1,...,xn> ψ
or
    logical formula (∀ x1,...,xn)( φ(x1,...,xn) → ψ(x1,...,xn) )
into a letter FST. The universal letter FST is assumed to defined over all letter pairs.
   

References

(to be added)

  -- AnssiYliJyra - 06 Oct 2008
Changed:
<
<
META TOPICMOVED by="KristerLinden" date="1212070604" from="KitWiki.HFSTTopicTemplate" to="KitWiki.HfstTopicTemplate"
>
>
META TOPICMOVED by="AnssiYliJyra" date="1223288854" from="KitWiki.HfstGeneralizedRestrictionAPI" to="KitWiki.HfstAPIGeneralizedRestrictionLayer"

Revision 12008-10-06 - AnssiYliJyra

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="HfstHome"

HFST: API for Generalized Restriction (GR) and Predicate Logic in FST Calculus

Type Function Comment hfst-lexc hfst-twolc
VarHandle create_var_type2 () Create a FO variable denoting pairs of positions in each string    
VarHandle create_var_type1 () Create a FO variable denoting independent positions in each string.    
VarHandle create_var_type3 () Create a FO variable denoting pairs of positions in each string (for marking a substring with sprinkled auxiliary symbols).    

Type Function Comment hfst-lexc hfst-twolc
LambdaExpHandle var_ismember (VarHandle x, TransducerHandle t) Asserts that sequence x is recognized by t.    
LambdaExpHandle var_has_context (VarHandle x, TransducerHandle rc, TransducerHandle rc, bool padded) Asserts that sequence x is surrounded by (padded) contexts lc and rc.    
LambdaExpHandle var_precedes (VarHandle x, TransducerHandle rc, bool padded) Asserts that substring x precedes (padded) right context rc.    
LambdaExpHandle var_follows (VarHandle x, TransducerHandle lc, bool padded) Asserts that substring x follows (padded) left context lc.    
LambdaExpHandle var_rename (VarHandle x, VarHandle y, LambdaExpHandle ψ) Makes α transformation for lambda expression ψ by replacing variable x with variable y.    
LambdaExpHandle var_interpret_gr (VarHandle m, LambdaExpHandle φ, LambdaExpHandle ψ) Compiles
    generalized restriction φ(x) =m> ψ(x)
or
    logical expression (∀ x)( φ(x) → ψ(x) )
into an FST without variable x. The universal letter FST is assumed to defined over all letter pairs and variable symbols.
   
TransducerHandle var_interpret_gr (LambdaExpHandle φ, LambdaExpHandle ψ) Compiles
    generalized restriction φ(x1,...,xn) =m> ψ(x1,...,xn)
or
    logical expression (∀ x1,...,xn)( φ(x1,...,xn) → ψ(x1,...,xn) )
into a letter FST. The universal letter FST is assumed to defined over all letter pairs.
   

<---
Variable harmonization is needed to combine two VarTransducers.  It compares the sets of variables used in transducers and inserts missing variables as loops to every state.

Concatenation means that we order variables on different sides of a position. Shuffle? Means adding loops without variables. Composition?

exists S(t1,x,t2) S(x, t1) s(t1, x) x_b = y_b x_e = y_b x_b < y_b x_e < y_b y_b < x_e y_e < x_e OL(x,y) x in t1

(contents of this page) -->


<--  
-->
-- AnssiYliJyra - 06 Oct 2008

META TOPICMOVED by="KristerLinden" date="1212070604" from="KitWiki.HFSTTopicTemplate" to="KitWiki.HfstTopicTemplate"
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback