[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/aclbulk-2009-hulden-revisiting-multi-tape-automata-semitic/)

[home](https://md.mova.elamur.ai/free/en/) / [docs](https://md.mova.elamur.ai/free/en/docs/) / [papers](https://md.mova.elamur.ai/free/en/docs/papers/) / [Ancient Hebrew](https://md.mova.elamur.ai/free/en/docs/papers/hbo/) / Revisiting Multi-Tape Automata for Semitic Morphological Analysis and Generation

# Revisiting Multi-Tape Automata for Semitic Morphological Analysis and Generation

**Authors:** [Mans Hulden](https://md.mova.elamur.ai/free/en/docs/papers/authors/mans-hulden/) · **Year:** 2009 · **Venue:** Proceedings of the EACL 2009 Workshop on Computational Approaches to Semitic Languages, pp. 19–26 **Link:** [aclanthology.org/W09-0803](https://aclanthology.org/W09-0803/) · library `aclbulk-2009-hulden-revisiting-multi-tape-automata-semitic` · **Licence:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) (ACL Anthology, before 2016) — summary only

[**8** citations](https://openalex.org/works?filter=cites:W2095185053) openalex-snapshot · 2026-10-14[**4** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/aclbulk-2009-hulden-revisiting-multi-tape-automata-semitic/) of the 140673 papers whose bibliographies we read[Proceedings of the EACL 2009 Workshop on Computational Approaches to Semitic Languages](https://aclanthology.org/volumes/W09-08/)[licence](https://creativecommons.org/licenses/by-nc-sa/3.0/)

- [Publisher's page](https://aclanthology.org/W09-0803/)
- [PDF](https://aclanthology.org/W09-0803.pdf)
- [DOI 10.3115/1621774.1621779](https://doi.org/10.3115/1621774.1621779)
- [OpenAlex](https://openalex.org/W2095185053)

**Authors (1)**

1. [Hulden, Mans](https://openalex.org/A5001438384) [Semantic Scholar](https://www.semanticscholar.org/author/1707857) · h 20 · 2106 citations · 145 works

Citations and author metrics from openalex-snapshot (2026-10-14); authors with the same name are not always told apart.

## What it is about

Root-and-pattern morphology fits a multi-tape automaton well, since the root, the vowel pattern, the template and the affixes can run on separate tapes. Hulden shows how to store such an automaton on a single tape that any standard finite-state toolkit can handle. Each tape symbol is marked with its tape number during construction, the tapes are interleaved with a blank symbol, and a homomorphism removes the markers at the end. Tape contents are generated as languages and then constrained by two-level-style rules, so that every root consonant must match an input consonant and a pattern vowel must match a vocalisation. The method is implemented in foma with a modified matcher and tested on Arabic verbs with about 2,000 roots. The paper notes that a naive 5-tape example has 5,056,506 transitions, which a few encoding tricks reduce to 97,126. With any trilateral root accepted, the Arabic grammar has about 2,000 states.

## Ideas

- I1. Interleaved tape storage for Hebrew verb stems: the input letters, the root consonants, the stem pattern and the affixes aligned position by position. The segmenter tables of `tools/hbo` could be produced from such aligned tapes, so that each segment carries its root and pattern for the parser to use.
- I2. Optional vowels inside patterns (C(V)C(V)C), so that one grammar parses pointed, partly pointed and unpointed words. This is the natural way to unify the two modes of `tools/hbo` instead of keeping two grammars.
- I3. A baseline: accept any trilateral root first, record the automaton size and the number of spurious roots, then add a root list and measure again. The difference is the cost of the missing lexicon, a number Mova can report honestly.

## For Mova

I1 goes into [The verb](https://md.mova.elamur.ai/free/en/docs/languages/hbo/06-verb/) (stem templates) and the segmenter of `tools/hbo`. I2 goes into [1. Script and pointing](https://md.mova.elamur.ai/free/en/docs/languages/hbo/01-script/) and the pointed/unpointed modes of `tools/hbo`. I3 is a measurement for `tools/hbo`. The same tape design is a candidate for Aramaic verbs in [The verb in Biblical Aramaic](https://md.mova.elamur.ai/free/en/docs/languages/arc/verbs/).

## Cite

The paper itself, not this card. BibTeX from the library's record of the work. [DOI 10.3115/1621774.1621779](https://doi.org/10.3115/1621774.1621779)

```
@inproceedings{hulden2009revisiting,
  title = {{Revisiting Multi-Tape Automata for Semitic Morphological Analysis and Generation}},
  author = {Hulden, Mans},
  booktitle = {Proceedings of the EACL 2009 Workshop on Computational Approaches to Semitic Languages},
  year = {2009},
  doi = {10.3115/1621774.1621779},
  url = {https://doi.org/10.3115/1621774.1621779}
}
```

- [← previous Semitic Morphological Analysis and Generation Using Finite State Transducers with Feature Structures](https://md.mova.elamur.ai/free/en/docs/papers/aclbulk-2009-gasser-semitic-morphological-analysis-generation-finite/)
- [next → How to Establish a Verbal Paradigm on the Basis of Ancient Syriac Manuscripts](https://md.mova.elamur.ai/free/en/docs/papers/aclbulk-2009-peursen-how-establish-verbal-paradigm-basis/)
- [↑ back to Ancient Hebrew](https://md.mova.elamur.ai/free/en/docs/papers/hbo/)

## References

22 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Beesley, K. and Karttunen, L. (2003). Finite-State Morphology. CSLI, Stanford. [find](https://scholar.google.com/scholar?q=Beesley%2C+K%2E+and+Karttunen%2C+L%2E+%282003%29%2E+Finite%2DState+Morphology%2E+CSLI%2C+Stanford%2E)
2. Beesley, K. R. (1996). Arabic finite-state analysis and generation. In COLING ’96. [find](https://scholar.google.com/scholar?q=Beesley%2C+K%2E+R%2E+%281996%29%2E+Arabic+finite%2Dstate+analysis+and+generation%2E+In+COLING+%E2%80%9996%2E)
3. Beesley, K. R. (1998a). Arabic morphology using only finite-state operations. In Proceedings of the Workshop on Computational Approaches to Semitic Languages COLING-ACL, pages 50– 57. [find](https://scholar.google.com/scholar?q=Beesley%2C+K%2E+R%2E+%281998a%29%2E+Arabic+morphology+using+only+finite%2Dstate+operations%2E+In+Proceedings+of+the+Workshop+on+Computational+Approaches+to+Semitic+Languages+COLING%2DACL%2C+pages+50%E2%80%93+57%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/aclbulk-1998-beesley-arabic-morphology-only-finite-state/)
4. Beesley, K. R. (1998b). Consonant spreading in Arabic stems. In ACL, volume 36, pages 117– 123. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Beesley%2C+K%2E+R%2E+%281998b%29%2E+Consonant+spreading+in+Arabic+stems%2E+In+ACL%2C+volume+36%2C+pages+117%E2%80%93+123%2E+Association+for+Computational+Linguistics%2E)
5. Beeston, A. F. L. (1968). Written Arabic: An approach to the basic structures. Cambridge University Press, Cambridge. [find](https://scholar.google.com/scholar?q=Beeston%2C+A%2E+F%2E+L%2E+%281968%29%2E+Written+Arabic%3A+An+approach+to+the+basic+structures%2E+Cambridge+University+Press%2C+Cambridge%2E)
6. Buckwalter, T. (2004). Arabic morphological analyzer 2.0. LDC. [find](https://scholar.google.com/scholar?q=Buckwalter%2C+T%2E+%282004%29%2E+Arabic+morphological+analyzer+2%2E0%2E+LDC%2E)
7. Habash, N. and Rambow, O. (2006). MAGEAD: A morphological analyzer and generator for the Arabic dialects. Proceedings of COLING-ACL 2006. [↗](https://doi.org/10.7916/d87s7x73) [our card](https://md.mova.elamur.ai/free/en/docs/papers/aclbulk-2006-habash-magead-morphological-analyzer-generator-arabic/)
8. Habash, N., Rambow, O., and Kiraz, G. (2005). Morphological analysis and generation for Arabic dialects. Proceedings of the Workshop on Computational Approaches to Semitic Languages (ACL ’05). [find](https://scholar.google.com/scholar?q=Habash%2C+N%2E%2C+Rambow%2C+O%2E%2C+and+Kiraz%2C+G%2E+%282005%29%2E+Morphological+analysis+and+generation+for+Arabic+dialects%2E+Proceedings+of+the+Workshop+on+Computational+Approaches+to+Semitic+Languages+%28ACL+%E2%80%9905%29%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/aclbulk-2005-habash-morphological-analysis-generation-arabic-dialects/)
9. Hulden, M. (2008). Regular expressions and predicate logic in finite-state language processing. [↗](https://doi.org/10.3233/978-1-58603-975-2-82)
10. In Piskorski, J., Watson, B., and Yli-Jyrä, A., editors, Proceedings of FSMNLP 2008. [find](https://scholar.google.com/scholar?q=In+Piskorski%2C+J%2E%2C+Watson%2C+B%2E%2C+and+Yli%2DJyra%CC%88%2C+A%2E%2C+editors%2C+Proceedings+of+FSMNLP+2008%2E)
11. Kataja, L. and Koskenniemi, K. (1988). Finite-state description of Semitic morphology: a case study of ancient Akkadian. In COLING ’88, pages 313–315. [find](https://scholar.google.com/scholar?q=Kataja%2C+L%2E+and+Koskenniemi%2C+K%2E+%281988%29%2E+Finite%2Dstate+description+of+Semitic+morphology%3A+a+case+study+of+ancient+Akkadian%2E+In+COLING+%E2%80%9988%2C+pages+313%E2%80%93315%2E)
12. Kay, M. (1987). Nonconcatenative finite-state morphology. In Proceedings of the third conference on European chapter of the Association for Computational Linguistics, pages 2–10. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Kay%2C+M%2E+%281987%29%2E+Nonconcatenative+finite%2Dstate+morphology%2E+In+Proceedings+of+the+third+conference+on+European+chapter+of+the+Association+for+Computational+Linguistics%2C+pages+2%E2%80%9310%2E+Association+for+Compu)
13. Kiraz, G. A. (1994). Multi-tape two-level morphology: A case study in Semitic non-linear morphology. In COLING ’94, pages 180–186. [↗](https://doi.org/10.48550/arxiv.cmp-lg/9407023) [our card](https://md.mova.elamur.ai/free/en/docs/papers/aclbulk-1994-kiraz-multi-tape-two-level-morphology/)
14. Kiraz, G. A. (2000). Multi-tiered nonlinear morphology using multitape finite automata: A case study on Syriac and Arabic. Computational Linguistics, 26(1):77–105. [find](https://scholar.google.com/scholar?q=Kiraz%2C+G%2E+A%2E+%282000%29%2E+Multi%2Dtiered+nonlinear+morphology+using+multitape+finite+automata%3A+A+case+study+on+Syriac+and+Arabic%2E+Computational+Linguistics%2C+26%281%29%3A77%E2%80%93105%2E)
15. Kiraz, G. A. (2001). Computational nonlinear morphology: with emphasis on Semitic languages. Cambridge University Press, Cambridge. [find](https://scholar.google.com/scholar?q=Kiraz%2C+G%2E+A%2E+%282001%29%2E+Computational+nonlinear+morphology%3A+with+emphasis+on+Semitic+languages%2E+Cambridge+University+Press%2C+Cambridge%2E)
16. Koskenniemi, K. (1983). Two-level morphology: A general computational model for word-form recognition and production. Publication 11, University of Helsinki, Department of General Linguistics, Helsinki. [find](https://scholar.google.com/scholar?q=Koskenniemi%2C+K%2E+%281983%29%2E+Two%2Dlevel+morphology%3A+A+general+computational+model+for+word%2Dform+recognition+and+production%2E+Publication+11%2C+University+of+Helsinki%2C+Department+of+General+Linguistics%2C+Helsink)
17. Lavie, A., Itai, A., and Ornan, U. (1988). On the applicability of two level morphology to the inflection of Hebrew verbs. In Proceedings of ALLC III, pages 246–260. [find](https://scholar.google.com/scholar?q=Lavie%2C+A%2E%2C+Itai%2C+A%2E%2C+and+Ornan%2C+U%2E+%281988%29%2E+On+the+applicability+of+two+level+morphology+to+the+inflection+of+Hebrew+verbs%2E+In+Proceedings+of+ALLC+III%2C+pages+246%E2%80%93260%2E)
18. McCarthy, J. J. (1981). A Prosodic Theory of Non-concatenative Morphology. Linguistic Inquiry, 12(3):373–418. [find](https://scholar.google.com/scholar?q=McCarthy%2C+J%2E+J%2E+%281981%29%2E+A+Prosodic+Theory+of+Non%2Dconcatenative+Morphology%2E+Linguistic+Inquiry%2C+12%283%29%3A373%E2%80%93418%2E)
19. van Noord, G. (2000). FSA 6 Reference Manual. [find](https://scholar.google.com/scholar?q=van+Noord%2C+G%2E+%282000%29%2E+FSA+6+Reference+Manual%2E)
20. Wehr, H. (1979). A Dictionary of Modern Written Arabic. Spoken Language Services, Inc., Ithaca, NY. [find](https://scholar.google.com/scholar?q=Wehr%2C+H%2E+%281979%29%2E+A+Dictionary+of+Modern+Written+Arabic%2E+Spoken+Language+Services%2C+Inc%2E%2C+Ithaca%2C+NY%2E)
21. Yli-Jyrä, A. and Koskenniemi, K. (2004). Compiling contextual restrictions on strings into finite-state automata. The Eindhoven FASTAR Days Proceedings. [find](https://scholar.google.com/scholar?q=Yli%2DJyra%CC%88%2C+A%2E+and+Koskenniemi%2C+K%2E+%282004%29%2E+Compiling+contextual+restrictions+on+strings+into+finite%2Dstate+automata%2E+The+Eindhoven+FASTAR+Days+Proceedings%2E)
22. Yona, S. and Wintner, S. (2008). A finite-state morphological grammar of Hebrew. Natural Language Engineering, 14(2):173–190. [↗](https://doi.org/10.1017/s1351324906004384) [our card](https://md.mova.elamur.ai/free/en/docs/papers/aclbulk-2005-yona-finite-state-morphological-grammar-hebrew/)