Systems and methods for determining the determinizability of finite-state automata and transducers

Number of patents in Portfolio can not be more than 2000

United States of America Patent

PATENT NO 7783485
APP PUB NO 20070299668A1
SERIAL NO

11771471

Stats

ATTORNEY / AGENT: (SPONSORED)

Importance

Loading Importance Indicators... loading....

Abstract

See full text

Finite-state transducers and weighted finite-state automata may not be determinizable. The twins property can be used to characterize the determinizability of such devices. For a weighted finite-state automaton or transducer, that weighted finite-state automaton or transducer and its inverse are intersected or composed, respectively. The resulting device is checked to determine if it has the cycle-identity property. If not, the original weighted finite-state automaton or transducer is not determinizable. For a weighted or unweighted finite-state transducer, that device is checked to determine if it is functional. If not, that device is not determinizable. That device is then composed with its inverse. The composed device is checked to determine if every edge in the composed device having a cycle-accessible end state meets at least one of a number of conditions. If so, the original device has the twins property. If the original device has the twins property, then it is determinizable.

Loading the Abstract Image... loading....

First Claim

See full text

Family

Loading Family data... loading....

Patent Owner(s)

  • AT&T INTELLECTUAL PROPERTY II, L.P.

International Classification(s)

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Allauzen, Cyril New York, US 6 50
Mohri, Mehryar New York, US 32 1308

Cited Art Landscape

Load Citation

Patent Citation Ranking

Forward Cite Landscape

Load Citation