A FILTER-BASED ALGORITHM FOR EFFICIENT COMPOSITION OF FINITE-STATE TRANSDUCERS

DOI10.1142/S0129054111009033zbMath1234.68191OpenAlexW2149286198MaRDI QIDQ3224948

Cyril Allauzen, Michael D. Riley, Johan Schalkwyk

Publication date: 13 March 2012

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054111009033

zbMATH Keywords

reachabilitylookaheadepsilon transitionsweighted finite-state transducerscomposition filtersfinite-state composition

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the consecutive ones property
• PC trees and circular-ones arrangements.
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• GENERAL ALGORITHMS FOR TESTING THE AMBIGUITY OF FINITE AUTOMATA AND THE DOUBLE-TAPE AMBIGUITY OF FINITE-STATE TRANSDUCERS

This page was built for publication: A FILTER-BASED ALGORITHM FOR EFFICIENT COMPOSITION OF FINITE-STATE TRANSDUCERS