A disambiguation algorithm for finite automata and functional transducers

Mehryar Mohri

doi:10.1007/978-3-642-31606-7_23

A disambiguation algorithm for finite automata and functional transducers

Mehryar Mohri

Computer Science

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

Abstract

We present a new disambiguation algorithm for finite automata and functional finite-state transducers. We give a full description of the algorithm, including a detailed pseudocode and analysis, and several illustrating examples. Our algorithm is often more efficient and the result dramatically smaller than the one obtained using determinization for finite automata or an existing disambiguation algorithm for transducers based on a construction of Schützenberger. In a variety of cases, the size of the unambiguous transducer returned by our algorithm is only linear in that of the input transducer while the transducer given by the construction of Schützenberger is exponentially larger. Our algorithm can be used effectively in many applications to make automata and transducers more efficient to use.

Original language	English (US)
Title of host publication	Implementation and Application of Automata - 17th International Conference, CIAA 2012, Proceedings
Pages	265-277
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-642-31606-7_23
State	Published - 2012
Event	17th International Conference on Implementation and Application of Automata, CIAA 2012 - Porto, Portugal Duration: Jul 17 2012 → Jul 20 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7381 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	17th International Conference on Implementation and Application of Automata, CIAA 2012
Country/Territory	Portugal
City	Porto
Period	7/17/12 → 7/20/12

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-31606-7_23

Cite this

Mohri, M. (2012). A disambiguation algorithm for finite automata and functional transducers. In Implementation and Application of Automata - 17th International Conference, CIAA 2012, Proceedings (pp. 265-277). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7381 LNCS). https://doi.org/10.1007/978-3-642-31606-7_23

A disambiguation algorithm for finite automata and functional transducers. / Mohri, Mehryar.
Implementation and Application of Automata - 17th International Conference, CIAA 2012, Proceedings. 2012. p. 265-277 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7381 LNCS).

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

Mohri, M 2012, A disambiguation algorithm for finite automata and functional transducers. in Implementation and Application of Automata - 17th International Conference, CIAA 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7381 LNCS, pp. 265-277, 17th International Conference on Implementation and Application of Automata, CIAA 2012, Porto, Portugal, 7/17/12. https://doi.org/10.1007/978-3-642-31606-7_23

Mohri M. A disambiguation algorithm for finite automata and functional transducers. In Implementation and Application of Automata - 17th International Conference, CIAA 2012, Proceedings. 2012. p. 265-277. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-31606-7_23

@inproceedings{ef5e60ca449c4d9683480b8e2d9d7fc8,

title = "A disambiguation algorithm for finite automata and functional transducers",

abstract = "We present a new disambiguation algorithm for finite automata and functional finite-state transducers. We give a full description of the algorithm, including a detailed pseudocode and analysis, and several illustrating examples. Our algorithm is often more efficient and the result dramatically smaller than the one obtained using determinization for finite automata or an existing disambiguation algorithm for transducers based on a construction of Sch{\"u}tzenberger. In a variety of cases, the size of the unambiguous transducer returned by our algorithm is only linear in that of the input transducer while the transducer given by the construction of Sch{\"u}tzenberger is exponentially larger. Our algorithm can be used effectively in many applications to make automata and transducers more efficient to use.",

author = "Mehryar Mohri",

note = "Copyright: Copyright 2012 Elsevier B.V., All rights reserved.; 17th International Conference on Implementation and Application of Automata, CIAA 2012 ; Conference date: 17-07-2012 Through 20-07-2012",

year = "2012",

doi = "10.1007/978-3-642-31606-7_23",

language = "English (US)",

isbn = "9783642316050",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "265--277",

booktitle = "Implementation and Application of Automata - 17th International Conference, CIAA 2012, Proceedings",

}

TY - GEN

T1 - A disambiguation algorithm for finite automata and functional transducers

AU - Mohri, Mehryar

PY - 2012

Y1 - 2012

N2 - We present a new disambiguation algorithm for finite automata and functional finite-state transducers. We give a full description of the algorithm, including a detailed pseudocode and analysis, and several illustrating examples. Our algorithm is often more efficient and the result dramatically smaller than the one obtained using determinization for finite automata or an existing disambiguation algorithm for transducers based on a construction of Schützenberger. In a variety of cases, the size of the unambiguous transducer returned by our algorithm is only linear in that of the input transducer while the transducer given by the construction of Schützenberger is exponentially larger. Our algorithm can be used effectively in many applications to make automata and transducers more efficient to use.

AB - We present a new disambiguation algorithm for finite automata and functional finite-state transducers. We give a full description of the algorithm, including a detailed pseudocode and analysis, and several illustrating examples. Our algorithm is often more efficient and the result dramatically smaller than the one obtained using determinization for finite automata or an existing disambiguation algorithm for transducers based on a construction of Schützenberger. In a variety of cases, the size of the unambiguous transducer returned by our algorithm is only linear in that of the input transducer while the transducer given by the construction of Schützenberger is exponentially larger. Our algorithm can be used effectively in many applications to make automata and transducers more efficient to use.

UR - http://www.scopus.com/inward/record.url?scp=84866669764&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84866669764&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-31606-7_23

DO - 10.1007/978-3-642-31606-7_23

M3 - Conference contribution

AN - SCOPUS:84866669764

SN - 9783642316050

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 265

EP - 277

BT - Implementation and Application of Automata - 17th International Conference, CIAA 2012, Proceedings

T2 - 17th International Conference on Implementation and Application of Automata, CIAA 2012

Y2 - 17 July 2012 through 20 July 2012

ER -

A disambiguation algorithm for finite automata and functional transducers

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this