Computational Linguistics Problems Explained: Encodings, Sort Orders and Rule Machines (2026)

Some linguistics olympiad problems are not really about a language. They are about a procedure: an encoding to break, a sort order to reconstruct, a chain of rewrite rules to run, an ambiguity to enumerate. NACLO — the North American Computational Linguistics Open Competition — puts computational linguistics in its name. You still solve all of it with a pencil.

What makes a problem “computational” — and why it is not coding

Start with a fact that settles the question. The official IOL FAQ tells contestants to bring “pencils, sharpeners and erasers”, and lists mobile phones, smartphones, tablets and laptops among the forbidden items (confirm current details on ioling.org). Whatever the problem asks you to compute, you compute it by hand, in a six-hour paper containing, per the same FAQ, “precisely five problems”.

So the word “computational” does not mean “write a program”. It means the object of study is a procedure rather than a pattern: something with inputs, steps, an order of operations, and an output you can check. Where a classic morphology problem asks “what rule generates these forms?”, an algorithmic problem asks “what machine generates these forms, and what does it do to an input it has never seen?”

This matters for two groups of readers in particular. If you are a maths or CS student who has been told linguistics olympiads are for language people, this is the family that will feel immediately familiar — the reasoning is closer to tracing an algorithm than to knowing vocabulary. And if you are a humanities student who finds these problems alien, the good news is that they are the most trainable family in the whole contest: procedures can be drilled in a way that raw pattern intuition cannot. If you are still deciding whether the contest suits you at all, our overview of what the International Linguistics Olympiad is is the place to start.

Five algorithmic families

These are the recurring shapes, not an official taxonomy. The published problem sets on ioling.org are browsable by year, so you can check which of these turn up in any given edition rather than taking our word for it.

Worked example 1: a rule cascade, and why order decides the answer

Invented data for a language we will call Tesk — not a past problem. Underlying forms on the left, actual pronounced forms on the right: taba → tap; gede → get; mozu → mos.

Two rules are clearly involved. R1 deletes the final vowel. R2 devoices a final obstruent — b becomes p, d becomes t, z becomes s. Most solvers find both rules within a couple of minutes. The marks are in what comes next.

Now reverse the order. Apply R2 first: taba has no final obstruent — its last segment is a vowel — so nothing happens. Then apply R1: you get tab, ged, moz. Every prediction is wrong, using two rules that are individually correct.

That is the whole lesson of this family. Once more than one process is in play, “which rules?” is only half the question; “in what order, and how do I know?” is the other half, and the evidence for the ordering is usually a single item that only comes out right under one sequence. Naming that item explicitly is also, not coincidentally, one of the features that distinguishes a genuinely well-written solution from a merely correct one.

Worked example 2: reconstructing a sort order

Suppose a problem gives you a dictionary extract from an invented language, already in that dictionary’s own order, and asks you to insert new words correctly. The relevant stretch of the alphabet turns out to run: a, ä, b, c, ch, d, i, k, l, ll, o, s, t, u, with the remaining letters omitted here. Two things are doing the damage here: ch and ll are single letters with their own slots, and ä is a separate letter placed immediately after a rather than being treated as a variant of it.

The method is mechanical once you see it. Take consecutive pairs from the given list and ask what each pair proves: casa before cinta proves a before i; cinta before chalo proves that ch is not simply c followed by h, because otherwise chalo would have come before cinta. Each adjacent pair is one constraint, and the constraints together pin down the alphabet. Write the alphabet out explicitly before you file a single new word — that ordered list, stated once, is both your working tool and the core of your answer.

Do you need to be a programmer? Three habits that transfer, and three that do not

The IOL’s own description of its problems stresses “logical ability, patient work, and a willingness to think outside the box”, and states that no prior knowledge of linguistics is necessary. Nothing in that requires code — but some programming habits are genuinely useful.

• Trace tables transfer. Writing a column per rule and walking each input through them, as in the Tesk table above, is exactly what you would do to debug a function. It is the single most useful habit in this family.
• Invariants transfer. “Every output has an odd number of marks”, “the suffix never attaches to a vowel-final stem” — one invariant kills a dozen wrong hypotheses cheaply.
• Edge-case instinct transfers. The empty case, the one-element case, the case where two rules could both apply. Problem authors put the decisive evidence exactly there.
• Brute force does not transfer. You have no machine and roughly seventy minutes per problem. If your approach needs you to enumerate hundreds of possibilities, it is the wrong approach.
• “It works, ship it” does not transfer. An untested guess that happens to fit is worth far less than a stated rule with evidence, because the marks live in the write-up as well as the answer.
• Silent reasoning does not transfer. Code that runs correctly needs no commentary; a solution does. Whatever you worked out in your head has to reach the page.

How to fit this family into your season

Two practical points. First, algorithmic problems reward drilling more predictably than any other type, so they are a sensible place to spend early-season hours when your feel for unfamiliar languages is still thin. Build the trace-table habit on rule-cascade problems, then the constraint-collection habit on ordering problems; both are transferable techniques rather than facts to memorise. Our past problems practice pack lets you sort your practice by type so you can run several of one family in a row, which is how the pattern-recognition gets built.

Second, do not over-index on it. This is one family among several on a five-problem paper, and a student who only trains procedures will be exposed the moment a problem asks for patient work on unfamiliar morphology. Slot it as one strand inside a balanced cycle — the structure of our twelve-week study plan assumes exactly that kind of rotation.

Finally, if you are heading toward the North American route specifically, treat the competition’s own site as the authority on its current format, rounds and eligibility rather than any secondary description, including this one: confirm on naclo.org, and confirm anything about the international contest on ioling.org.

Frequently asked questions

Do computational linguistics problems require programming?
No. Per the IOL FAQ, contestants bring pencils, sharpeners and erasers, and laptops, tablets and phones are forbidden, so every procedure is executed by hand.

What does NACLO stand for?
The North American Computational Linguistics Open Competition. For its current format, rounds and eligibility, confirm on naclo.org.

Does a CS background give you an advantage?
Trace tables, invariants and edge-case instinct transfer well. Brute-force search does not, and neither does leaving your reasoning unwritten.

How do I know which rule applies first?
Find the item that comes out right under only one ordering, then cite it. That item is both your proof and the strongest sentence in your write-up.

IOL Club is an independent guide operated by Hanlin Education for China-based international-school students. We are NOT affiliated with, endorsed by, or sponsored by the IOL Board, NACLO or any national organiser. All data sets in this article are invented for teaching and are not reproduced past problems. Formats, rules and eligibility change: confirm current details on ioling.org before acting on anything here. Errors reported to our editorial desk are corrected within 7 working days.