Large scale inference of deterministic transductions: Tenjinno problem 1

Alexander Clark

Large scale inference of deterministic transductions: Tenjinno problem 1

Alexander Clark

Philosophy

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

3 Citations (Scopus)

Abstract

We discuss the problem of large scale grammatical inference in the context of the Tenjinno competition, with reference to the inference of deterministic finite state transducers, and discuss the design of the algorithms and the design and implementation of the program that solved the first problem. Though the OSTIA algorithm has good asymptotic guarantees for this class of problems, the amount of data required is prohibitive. We therefore developed a new strategy for inferring large scale transducers that is more adapted for large random instances of the type in question, which involved combining traditional state merging algorithms for inference of finite state automata with EM based alignment algorithms and state splitting algorithms.

Original language	Undefined/Unknown
Title of host publication	Proceedings of the 8th International Colloquium on Grammatical Inference (ICGI)
Pages	227-239
Number of pages	13
Volume	4201 LNAI
Publication status	Published - 2006

Cite this

@inbook{6d96c3b0a8a54fc19c5e2ec0fd068165,

title = "Large scale inference of deterministic transductions: Tenjinno problem 1",

abstract = "We discuss the problem of large scale grammatical inference in the context of the Tenjinno competition, with reference to the inference of deterministic finite state transducers, and discuss the design of the algorithms and the design and implementation of the program that solved the first problem. Though the OSTIA algorithm has good asymptotic guarantees for this class of problems, the amount of data required is prohibitive. We therefore developed a new strategy for inferring large scale transducers that is more adapted for large random instances of the type in question, which involved combining traditional state merging algorithms for inference of finite state automata with EM based alignment algorithms and state splitting algorithms.",

author = "Alexander Clark",

year = "2006",

language = "Undefined/Unknown",

volume = "4201 LNAI",

pages = "227--239",

booktitle = "Proceedings of the 8th International Colloquium on Grammatical Inference (ICGI)",

}

TY - CHAP

T1 - Large scale inference of deterministic transductions: Tenjinno problem 1

AU - Clark, Alexander

PY - 2006

Y1 - 2006

N2 - We discuss the problem of large scale grammatical inference in the context of the Tenjinno competition, with reference to the inference of deterministic finite state transducers, and discuss the design of the algorithms and the design and implementation of the program that solved the first problem. Though the OSTIA algorithm has good asymptotic guarantees for this class of problems, the amount of data required is prohibitive. We therefore developed a new strategy for inferring large scale transducers that is more adapted for large random instances of the type in question, which involved combining traditional state merging algorithms for inference of finite state automata with EM based alignment algorithms and state splitting algorithms.

AB - We discuss the problem of large scale grammatical inference in the context of the Tenjinno competition, with reference to the inference of deterministic finite state transducers, and discuss the design of the algorithms and the design and implementation of the program that solved the first problem. Though the OSTIA algorithm has good asymptotic guarantees for this class of problems, the amount of data required is prohibitive. We therefore developed a new strategy for inferring large scale transducers that is more adapted for large random instances of the type in question, which involved combining traditional state merging algorithms for inference of finite state automata with EM based alignment algorithms and state splitting algorithms.

M3 - Conference paper

VL - 4201 LNAI

SP - 227

EP - 239

BT - Proceedings of the 8th International Colloquium on Grammatical Inference (ICGI)

ER -