Glushkov's construction for functional subsequential transducers
Glushkov's construction has many interesting properties and they become even more evident when applied to transducers. This article strives to show the wast range of possible extensions and optimisations for this algorithm. Special flavour of regular expressions is introduced, which can be efficiently converted to $\epsilon$-free functional subsequential weighted finite state transducers. Produced automata are very compact, as they contain only one state for each symbol (from input alphabet) of original expression and only one transition for each range of symbols, no matter how large. Such compactified ranges of transitions allow for efficient binary search lookup during automaton evaluation. All the methods and algorithms presented here were used to implement open-source compiler of regular expressions for multitape transducers.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Active Learning of Sequential Transducers with Side Information about the Domain
Active learning is a setting in which a student queries a teacher, through membership and equivalence queries, in order to learn a language. Performance on these algorithms is often measured in the number of queries requ…
Active LearningHome Automation System based on Intelligent Transducer Enablers
This paper presents a novel home automation system named HASITE (Home Automation System based on Intelligent Transducer Enablers), which has been specifically designed to identify and configure transducers easily and qui…
Vowel Harmony and Subsequentiality
Bounded copying is subsequential: Implications for metathesis and reduplication
Spatial response identification enables robust experimental ultrasound computed tomography
Ultrasound computed tomography techniques have the potential to provide clinicians with 3D, quantitative and high-resolution information of both soft and hard tissues such as the breast or the adult human brain. Their pr…