Line: 1 to 1 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

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

Line: 17 to 17 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## Basic Notions
## Auxiliary Marker Symbols | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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:`◊` . These auxiliary symbols occur in strings of marker-augmented FSTs that we call below_{1}, ◊_{2},..., <x>, <y>, ... (x), (y),..., x, y, ...*over FSTs*(interfaced through`OvertFstHandle` ). The data type of an uncompiled generalized restriction is`OvertFstPair` . - 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` . - 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).
- 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. - 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). - 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:`◊` . These auxiliary symbols occur in strings of marker-augmented FSTs that we call_{1}, ◊_{2},..., <x>, <y>, ... (x), (y),..., x, y, ...*overt FSTs*(interfaced through`OvertFstHandle` ). The data type of an uncompiled generalized restriction is`OvertFstPair` . - The size of th auxiliary symbol alphabet may vary dynamically.
- Most applications use only one or two kinds of auxiliary symbols, but they may need a few more (a few dozens of them).
- 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*. - 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.
- Unknown auxiliary symbols have to added by
*harmonization*in some situations:- 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. - 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.
- When an FST is combined under
All auxiliary symbol are neither used to mark things in similar ways and they are not used to mark similar things. - 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:
- It occurs in specified positions and is used as a joiner rather than a substring marker.
- It occurs a bounded number of times (typically 2) and mark substrings.
- It occurs freely in specified positions that may be finite of infinit.
- All auxiliary symbols used in the current layer have are interfaced through a
`VarHandle` .- 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. - The
`VarHandle` that is stored to the marker alphabet of*over FSTs*containts additional information on usage mode of the symbol.
- Each
- The functions in the GR layer may test that the relevant
`VarHandles` have a correct usage mode.- The current layer supports only one kind of auxiliary symbols: those that are used in pairs to mark substrings.
- 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 - 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.
- 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 TransducersOften 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-
`VarHandle` can contain a`KeyHandle` rather than a`SymbolHandle` and it probably more feasible to implement that way. - 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.
- 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. - 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. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Line: 42 to 59 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Changed: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

< < | ## Function Primitives## Definition of Substring Variables and other Diamond Symbols | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

> > | The current layer contains a few sets of functions: - 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
- 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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Changed: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

< < |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

> > |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Changed: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

< < | ## Functions That Relate Substring Variables to Variable-Free Conditions
## Functions That Compare or Rename Substring Variables | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

> > | ## Functions That Relate Joiner Variables to FSTs | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Changed: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

< < |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

> > |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## Functions That Implement Logical Connectors and Quantifiers
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Changed: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

< < |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

> > |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Changed: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

< < | ## Functions That Construct, Combine and Compile GR Rules | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

> > | ## Function Supporting Substring Variables | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Changed: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

< < |
## Derived Functions
## Functions That Compile Constraints using GR Rules
In the following,
## GR-Based Engines for Grammar SystemsThe 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 |

View topic | History: r11 < r10 < r9 < r8 | More topic actions...

Copyright © 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

Ideas, requests, problems regarding TWiki? Send feedback