---
title: "Revisiting Multi-Tape Automata for Semitic Morphological Analysis and Generation — Hulden 2009"
description: "Hulden shows how to store such an automaton on a single tape that any standard finite-state toolkit can handle. 22 references, cited by 4 papers here."
authors: ["Mans Hulden"]
year: 2009
venue: "Proceedings of the EACL 2009 Workshop on Computational Approaches to Semitic Languages"
source: "https://aclanthology.org/W09-0803/"
doi: "10.3115/1621774.1621779"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/hulden-2009-revisiting-multi-tape-automata-semitic/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/hulden-2009-revisiting-multi-tape-automata-semitic/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2009](https://md.research.elamur.ai/free/en/papers/2009/) / 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.research.elamur.ai/free/en/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, 2026-10-14 · **4** citations in our library of the 140,884 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 · 2,106 citations · 145 works

Citations and author metrics: OpenAlex, 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.

## For Mova

- 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.

I1 goes into [languages/hbo/06-verb.md](https://mova.elamur.ai/free/en/docs/languages/hbo/06-verb/) (stem templates) and the segmenter of `tools/hbo`. I2 goes into [languages/hbo/01-script.md](https://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 [languages/arc/verbs.md](https://mova.elamur.ai/free/en/docs/languages/arc/verbs/).

## Institutions

[🎓**University of Arizona** Tucson · United States 15 works · 9,997 citations](https://md.research.elamur.ai/free/en/universities/university-of-arizona/)

Topics[Morphology](https://md.research.elamur.ai/free/en/topics/morphology/) · [Semitic languages](https://md.research.elamur.ai/free/en/topics/semitic-languages/)

## Cite

Cite as Mans Hulden. 2009. Revisiting Multi-Tape Automata for Semitic Morphological Analysis and Generation. Proceedings of the EACL 2009 Workshop on Computational Approaches to Semitic Languages.

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)

```bibtex
@inproceedings{hulden2009revisiting,
  title = {{Revisiting Multi-Tape Automata for Semitic Morphological Analysis and Generation}},
  author = {Mans Hulden},
  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 Multi-word expressions in textual inference: Much ado about nothing?](https://md.research.elamur.ai/free/en/papers/marneffe-2009-multi-word-expressions-textual-inference/)
- [next → Descriptive and Empirical Approaches to Capturing Underlying Dependencies among Parsing Errors](https://md.research.elamur.ai/free/en/papers/hara-2009-descriptive-empirical-approaches-capturing-underlying/)
- [↑ back to papers of 2009](https://md.research.elamur.ai/free/en/papers/2009/)

## 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. [our card](https://md.research.elamur.ai/free/en/papers/beesley-1998-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. [our card](https://md.research.elamur.ai/free/en/papers/habash-2006-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). [our card](https://md.research.elamur.ai/free/en/papers/habash-2005-morphological-analysis-generation-arabic-dialects/)
9. Hulden, M. (2008). Regular expressions and predicate logic in finite-state language processing. [find](https://scholar.google.com/scholar?q=Hulden%2C+M%2E+%282008%29%2E+Regular+expressions+and+predicate+logic+in+finite%2Dstate+language+processing%2E)
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. [our card](https://md.research.elamur.ai/free/en/papers/kiraz-1994-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. [our card](https://md.research.elamur.ai/free/en/papers/yona-2005-finite-state-morphological-grammar-hebrew/)