Glossary of Formal Languages and Compilation

An index of all technical terms used in this article series, sorted alphabetically.

A

3-3-2 Pattern
A rhythmic grouping of 3+3+2 = 8 beats, typical of rumba, son cubano, and many popular music styles. The asymmetry creates a characteristic rhythmic tension between the groups of 3 and the final group of 2.
→ See M12

\stretch
SuperCollider key that multiplies the duration of each event by a factor. \stretch, 0.75 compresses time by 25%. Used for translating polymetric expressions (\stretch = M/N).
→ See B7

Action (CCS)
an observable event that a process can perform. Three types: action $$a$$ , co-action $\bar{a}$ , internal action $\tau$ .
→ See L12

Additive signature
Rhythmic signature that explicitly states internal groupings (e.g., 3+3+2/8 instead of 8/8). Essential for Indian tālas and aksak rhythms.
→ See B5

Adjunction
Central operation of TAGs. Consists of inserting an auxiliary tree at an internal node of an existing tree, by “cutting” the subtree and reattaching it to the foot node. This is what distinguishes TAGs from CFGs.
→ See L9

Aftertouch
pressure exerted on a key after the initial attack. Allows adding expression to sustained notes (vibrato, crescendo…).
→ See I4

Aksak
Turkish term meaning “limping.” Refers to asymmetrical rhythms common in Turkey and the Balkans (e.g., 2+2+2+3).
→ See B5

Alphabet (V or Σ)
Finite set of symbols usable in a grammar. Σ often denotes terminals alone, V the complete set.
→ See B2

Alter
Modification of a note’s pitch in MusicXML (sharp ♯ = +1, flat ♭ = -1, natural ♮ = 0).
→ See I5

Ambiguity (grammar)
A property of a grammar where the same string can be derived in several different ways (multiple possible parse trees).
→ See B1

ANAL (mode)
Analytical mode of the Bol Processor — the grammar tests if a sequence belongs to the language (modus tollens).
→ See L13

Analysis-by-synthesis
A recognition paradigm where the receiver generates internal candidates and compares them to the received signal. Analysis contains synthesis as a subprocess.
→ See L13

Arpeggio
notes of a chord played successively rather than simultaneously
→ See M3

Articulation
Indication of how a note is to be played (staccato, accent, tenuto…).
→ See I5

Assertion
a logical property about the program state at a given point. Preconditions and postconditions are assertions.
→ See L8

AST (Abstract Syntax Tree)
A tree-like, structured representation of source code, independent of textual syntax. The BP3 AST has a BPFile node as its root.
→ See B7

Axiom
an inference rule without premises (conclusion always true). Example: ⟨n⟩ ⇓ n is an axiom because a number always evaluates to itself.
→ See L6, L8

Ālāp
Opening of a raga where notes are introduced progressively (Sa, then Sa-Re, then Sa-Re-Ga…). Its accumulative structure exceeds the capabilities of flags (counters) and requires the context-sensitive extensions of BP3 (B6).
→ See B4, B6

Āvart
A complete cycle of tāla. A kayda can extend over several āvart before concluding with a tihāī.
→ See B4

B

Behaviorism
A school of psychology (early 20th century) that explains learning solely through stimulus-response, without reference to innate mental structures.
→ See M4

Big-step
semantics where a transition (denoted ⇓) completely evaluates an expression to its final value.
→ See L6

Bisimulation
a relation between two processes such that at each step, any action of one can be mimicked by the other, and vice versa. Finer than trace equivalence: it takes into account the branching structure.
→ See L11, L12

Bit
elementary unit of information (0 or 1). 7 bits = 128 possible values (0-127).
→ See I4

BNF (Backus-Naur Form)
notation for describing language syntax. e ::= n | e + e means “e is either n, or e + e”.
→ See L6

BNF / EBNF (Backus-Naur Form / Extended BNF): notation for writing formal grammars. Used to specify the syntax of programming languages. See L3.

Context-free

a type of grammar (Type 2) where each rule replaces a single symbol, independently of the context. Allows recursion and nesting. See L2.
→ See M1

Bol
A mnemonic syllable of the Indian tabla (e.g., dha, dhin, tin, ta). The “Bol” in “Bol Processor”.
→ See B1, B5, B6, B7, M5

Bol (बोल): Mnemonic syllable of the tabla (e.g., dha, dhin, tin, ta). The “Bol” in “Bol Processor”. Each bol corresponds to a specific stroke producing a distinct timbre.

String (or word)

Finite sequence of symbols. Example: “abc” is a string of 3 symbols.
→ See B2

Bottom (⊥)
minimal element of a domain, representing absence of information or non-termination. Pronounced “bottom”. Example: an infinite loop has ⊥ as its denotation.
→ See L7

Bottom-up parser
A parser that starts from the text and ascends towards the start symbol by reducing groups of symbols.
→ See L1

BP3
Bol Processor 3 — musical grammar software developed by Bernard Bel (see I2)
→ See M3

BP3 (Bol Processor 3)
Musical grammar software developed by Bernard Bel (1990s), designed for Indian and African music.
→ See M4, M5

BPFile
The root node of the BP3 AST, containing headers (file references, comments) and grammar blocks.
→ See B7

BPM
Beats Per Minute. Measure of tempo. 120 BPM = 120 quarter notes per minute.
→ See I4

C

∧ (conjunction)
logical connector “and”. P ∧ Q is true if and only if P and Q are both true.
→ See L8

Cadence
A sequence of chords that punctuates the end of a musical phrase (e.g., V → I = dominant → tonic).
→ See M4, M6

Cartesian product
A × B = set of all pairs (a, b) with a in A and b in B.
→ See L6

Categorical (distribution)
Discrete probability distribution over a finite set of categories, each with its own weight. Generalizes the roll of a loaded die to an arbitrary number of faces.
→ See B4

CCG (Combinatory Categorial Grammar)
Grammatical formalism where each word carries a typed category (like (S\NP)/NP for a transitive verb) and words combine via operators (application, composition, type-raising).
→ See L9

CCS (Calculus of Communicating Systems): a process algebra introduced by Robin Milner (1980). Operators: prefix $$a.P$$ , choice $$P + Q$$ , parallel $P \mid Q$ , restriction $P \setminus \{a\}$ .

Parallel composition

operator $P \mid Q$ (CCS) or $P \parallel_A Q$ (CSP) that executes two processes simultaneously.
→ See L12

CCS (Calculus of Communicating Systems): process algebra introduced by Robin Milner (1980). Operators: prefix (a.P), choice (P + Q), parallel (P | Q), restriction ((new a) P).

Parallel composition

operator P | Q that executes P and Q simultaneously. Processes can synchronize on common actions.
→ See L11

CFG (Context-Free Grammar)
A grammar where each rule replaces a single non-terminal symbol, independently of the surrounding context.
→ See B1

Chomsky hierarchy
classification of formal languages into 4 types (Type 3 → Type 0) according to the increasing expressive power of the necessary grammars. See L1.
→ See M1

Chomsky, Noam
American linguist (born in 1928), founder of the theory of generative grammars.
→ See M4

Circularity
a situation where the dependency graph contains a cycle, making evaluation impossible. Detecting whether an attribute grammar can produce circular dependencies is DEXPTIME-complete.
→ See L10

Class Invariant
a property that must be true for any object of a class, at any observable time (between method calls).
→ See L8

Combinator
Combination operation in CCGs. The main ones are application (forward/backward), composition (B), and type-raising (T). They originate from Curry’s combinatory logic.
→ See L9

Compas
The rhythmic cycle of flamenco, structured by accents that define the identity of each palo (style). In rumba, the compas is a 4-beat cycle (or 8 eighth notes) with a 3-3-2 accent pattern.
→ See M12

Compiler correctness
property stating that compilation preserves meaning. Formally: the Morris diagram commutes.
→ See L11

Compositionality
property whereby the meaning of a composite expression depends only on the meaning of its components. Example: the meaning of “2 + 3” depends only on the meaning of “2”, “3”, and “+”.
→ See L5, L7

Concatenation
joining strings end-to-end. Denoted · (middle dot). "abc" · "def" = "abcdef".
→ See L6

Configuration
complete state of a program at a given instant (expression to evaluate + environment + memory). Notated ⟨e, σ⟩ where e is the expression and σ is the state.
→ See L5, L6

Configuration (SOS)
Tuple representing the complete state of the system during derivation. For BP3 with flags and weights: (σ, φ, t, w) — working string, flag environment, time, weight function.
→ See B4

Conjunct motion
Melodic movement by successive whole or half steps (C-D-E), as opposed to disjunct motion (leaps, like C-G).
→ See M6

Consonance/Dissonance
Consonance is the quality of a stable and “pleasant” sound (octave, fifth, major third). Dissonance is unstable and calls for resolution.
→ See M6

Context marker
BP3 construction that conditions the application of a rule on the presence of a symbol in the context.
→ See B6

Context-free
A property of a rule that applies regardless of the symbol’s environment. The replacement of A by xyz does not depend on what precedes or follows A.
→ See B1, L1, M2

Context-free grammar (CFG)
A grammar whose rules all have the form A → γ (a single non-terminal on the left).
→ See L1

Context-sensitive
Property of a grammar where the replacement of a symbol depends on its environment. Corresponds to Type 1 of Chomsky’s hierarchy.
→ See B6

Continuous function
a function that preserves the limits of increasing chains. Necessary for the existence of fixed points.
→ See L7

Control Change (CC)
message to modify continuous parameters (volume, pan, sustain…). Identified by a number (0-127) and a value (0-127).
→ See I4

Convergence
Property of a process that tends towards a final state. Decremental weights converge to 0, forcing termination.
→ See B4

Cross-references
Links between elements of a text where one element refers to another defined elsewhere (e.g., hyperlinks, footnotes).
→ See L1

Cross-rhythm
A rhythmic pattern where the accents of one voice systematically fall between those of another.
→ See M5

Cross-serial dependencies
Syntactic structure where two sequences of elements correspond element by element, like subjects and verbs in Dutch (A₁ A₂ A₃ B₁ B₂ B₃ where Aᵢ depends on Bᵢ).
→ See L9

CSP (Communicating Sequential Processes): a process algebra by Tony Hoare (1985). Synchronization by shared events, with three semantic models (traces, failures, failures-divergences).

Downbeat

the first beat of a measure — the natural synchronization point between musical voices.
→ See L12

CSP (Communicating Sequential Processes): process algebra introduced by Tony Hoare (1985). Synchronization on shared events, with three semantic levels (traces, failures, failures-divergences).

Commutative diagram

a diagram where all paths between two points yield the same result. For a compiler: interpret the source = compile then interpret the target.
→ See L11

D

· (double brackets)
standard notation for “the denotation function”. e reads as “the denotation of e” or “what e means mathematically”.
→ See L7

Data byte
a MIDI byte whose most significant bit is 0 (values 0-127). Carries message parameters (note, velocity, CC value…).
→ See M1

Dataflow
paradigm where computation is modeled as a graph of data flows between processing nodes
→ See M3

DAW
Digital Audio Workstation. Music production software (Ableton, Logic, FL Studio…).
→ See I4, M3

Decrement
Decrease in a value. In <50-12>, the decrement is 12: the weight loses 12 with each use.
→ See B4

Decremental weight
Weight associated with a rule that decreases after each use of that rule. BP3 notation: <N-M> (initial weight N, decrement M).
→ See B4

Denotation
the mathematical value (function, set, etc.) associated with an expression. Noted e for expression e.
→ See L7

Dependency graph
a directed graph whose nodes are attribute instances and whose edges represent dependencies between them. If it is acyclic, an evaluation order exists.
→ See L10

Derivation
A sequence of rule applications starting from the initial symbol (S) down to a string containing only terminals.
→ See B1, B2, B3, L6

Derivation Mode
In BP3, a global strategy for choosing and applying rules (ORD, RND, LIN, SUB, SUB1).
→ See B3

Derivation tree (parse tree)
A visual representation of a derivation, with the start symbol at the root and terminals at the leaves.
→ See B1

Design by Contract
a programming methodology where functions are annotated with preconditions, postconditions, and invariants. Invented by Bertrand Meyer (Eiffel, 1986).
→ See L8

Determined Rest
Rest of fixed duration, noted - in BP3. Corresponds to an explicit pause of one unit of time.
→ See B2

Deterministic
a system that always produces the same result with the same inputs
→ See M3

Disjoint
Two sets are disjoint if they have no elements in common.
→ See B2

Divisions
Number of subdivisions per quarter note, defines the temporal resolution of the file.
→ See I5

Djembe
A goblet-shaped drum originating from West Africa, played with the hands.
→ See M5

DOCTYPE
Declaration at the beginning of an XML file that indicates the schema (structure rules) used.
→ See I5

Domain
a mathematical structure with a partial order (⊑) and completeness properties; serves as a “value space” for programs.
→ See L7

Domain theory
branch of mathematics providing the necessary structures (ordered domains) to define the semantics of loops and recursion.
→ See L5

Dominant
The 5th degree of the scale (e.g., G in C major), which creates tension calling for resolution to the tonic.
→ See M4

Dominant (V)
The fifth degree of the scale, a chord of tension that calls for the tonic.
→ See M6

Downbeat
Strong beat, usually the first beat of a measure.
→ See M5

DSL
Domain-Specific Language — a programming language dedicated to a particular domain
→ See M3

DTD (Document Type Definition): an older XML validation format, corresponding to a local tree language. Superseded by XSD since MusicXML 4.0.

Tree grammar

a grammar that operates on trees rather than character strings. XML schemas are tree grammars.
→ See M2

Dunun
A family of two-headed cylindrical drums (dununba, sangban, kenkeni) playing patterns in West Africa.
→ See M5

Dynamic
Indication of sound intensity on the score (pp, p, mp, mf, f, ff — from softest to loudest).
→ See I5

Dynamic weight
In BP3, a numerical weight associated with a rule that changes (usually decreases) after each use of that rule.
→ See B1

E

Elaboration
A note or passage that “decorates” a structural note without changing its meaning.
→ See M6

embedInStream
SuperCollider method that inserts events from a pattern into a routine’s (Prout) stream, allowing dynamic flow control.
→ See B7

Emitter
The module that traverses the AST and generates the target code (here, SuperCollider). Also called code generator or backend.
→ See B7

Empty string (ε)
The string of zero length, containing no symbols. Noted ε (epsilon) or λ (lambda).
→ See B2

Encoder / Decoder
In Shannon’s model, the encoder transforms a message into a signal (generation), the decoder reconstructs the message from the signal (recognition). They are not symmetrical.
→ See L13

Enharmonic
in music, two notes of the same pitch but different spelling (C# = D♭). MIDI does not distinguish enharmonics.
→ See I4

Environment
a dictionary associating each variable with its value. Noted ρ (rho). Example: {x ↦ 5, y ↦ 10}.
→ See L7

Equal Temperament
tuning system dividing the octave into 12 equal semitones. Standard of modern Western music.
→ See I4

Event.silent(dur)
SuperCollider event that emits no sound for the duration dur. Used for tie continuations and Lambda nodes.
→ See B7

F

Fan-out
Parameter of MCFGs that measures the number of components a rule can manipulate simultaneously. Fan-out 1 = CFG, fan-out 2 = TAG.
→ See L9

Fifths
Number of alterations in the key signature, counted on the circle of fifths (positive = sharps ♯, negative = flats ♭).
→ See I5

Finite automaton
An abstract machine with a finite number of states, without external memory. Reads an input character by character and changes state according to transition rules.
→ See L1, M1

Fixed point
value x such that f(x) = x. Example: 0 is a fixed point of f(x) = x², because f(0) = 0. In semantics, used to define loops and recursion.
→ See L5, L7

Flag
Named variable attached to BP3 rules, serving as a conditional counter. Can be tested, assigned, incremented, or decremented.
→ See B4

Flag environment (φ)
Function that associates each flag name with its current integer value. Notation: φ(avart) = 4.
→ See B4

Formal language
A set of symbol strings defined by precise rules.
→ See L1

Formal Verification
the use of mathematical methods to prove that a system (software or hardware) satisfies its specification.
→ See L8

Frege, Gottlob
German logician (1848-1925), founder of modern logic, to whom the principle of compositionality is attributed.
→ See M4

Functional update
Operation that creates a new environment identical to the old one except for one variable. Notation: φ[avart ↦ 3] means “φ with avart changed to 3.”
→ See B4

G

General MIDI (GM)
standard defining 128 identically numbered sounds on all compatible devices.
→ See I4

Generative grammar
A set of formal rules capable of producing all valid structures of a language.
→ See M4

GPR (Grouping Preference Rule)
In GTTM, a preference rule for grouping notes into phrases.
→ See M4

GPR (Grouping Preference Rules)
Preference rules for grouping. They describe how we perceive boundaries between musical groups.
→ See M6

Graha bheda
Technique of raga transposition by shifting the fundamental note (Sa), giving rise to a new raga. Formalizable as a BP3 homomorphism.
→ See B6

Grammar
A set of rules for generating or recognizing a language. Defined by terminal symbols, non-terminal symbols, and production rules.
→ See L1, M1

GrammarBlock
AST node representing a grammar block with a mode (ORD, RND, LIN, SUB, SUB1), a preamble, and rules.
→ See B7

Grouping structure
Hierarchical organization of musical events into units (motifs, phrases, sections).
→ See M4

GTTM
Generative Theory of Tonal Music — Lerdahl and Jackendoff’s theory modeling musical perception
→ See M3

GTTM (A Generative Theory of Tonal Music)
Lerdahl and Jackendoff’s theory (1983) formalizing the perception of tonal music.
→ See M4

GTTM (Generative Theory of Tonal Music)
Generative Theory of Tonal Music, developed by Lerdahl and Jackendoff (1983).
→ See M6

Guaranteed termination
Property of a system that necessarily reaches a final state in a finite number of steps. Decremental weights guarantee a maximum of ceil(N/M) + 1 steps.
→ See B4

Guard
Condition that must be satisfied for a rule to apply. Flags in test mode (/avart/, /avart>2/) function as guards.
→ See B4

H

Head
The structurally most important note of a group. The other notes in the group are elaborations of the head.
→ See M6

Hemiola
Polymetry of 3 against 2 (or 2 against 3). The most common case of metric superposition.
→ See B5, M5

Hierarchy
Organization in nested levels (tree), where each element belongs to a higher-level element.
→ See M4

Hoare Logic
a formal system of triples {P} C {Q} and inference rules for proving program correctness. Introduced by C.A.R. Hoare in 1969.
→ See L8

Hoare triple
notation {P} C {Q} meaning “if P is true before C, then Q is true after”.
→ See L5, L8

HomoApply
AST node representing the application of a homomorphism. Three variants: MASTER (transformed source sequence), SLAVE (substitution table, integrated into MASTER), REF (label, not emitted).
→ See B7

Homomorphism
Function that transforms each symbol in a string according to a fixed mapping, preserving the structure (morphism of free monoids).
→ See B6, L11

HTML
HyperText Markup Language — markup language for web pages, a cousin of XML.
→ See I5

HTSPN (Hierarchical Time Stream Petri Nets): a hierarchical extension of timed Petri nets, used for interactive scores (Senac 1995, Allombert 2007).

Token

a marker in a place of a Petri net. Represents a resource, a state, or a position in the execution.
→ See L12

I

⟹ (implication)
logical connector “implies”. P ⟹ Q means “if P is true, then Q is true”.
→ See L8

IDyOM (Information Dynamics of Music): A statistical model of musical prediction based on corpus entropy. Models the listener as an inference machine.

Grammatical inference (grammar induction): The “third direction” — finding the grammar from examples of sentences. The inverse problem of formal language theory.
Modus ponens / modus tollens

In logic, modus ponens goes from rule to consequence (if A then B, A, therefore B — generative direction). Modus tollens goes from observation to premise (if A then B, B observed, therefore A plausible — analytical direction).
→ See L13

IEEE 1599
multilayer standard for musical representation with 6 synchronized XML layers
→ See M3

Increasing chain
a sequence of elements x₀ ⊑ x₁ ⊑ x₂ ⊑ ... where each element has “more information” than the previous one. Used to construct fixed points.
→ See L7

Inference rule
schema of the form “if these premises are true, then this conclusion is true”.
→ See L5, L6

Inherited attribute
an attribute whose value is transmitted by the parent node or siblings located to the left. Information flows top-down or left-to-right. Example: the declared type type_decl in a list of variables.
→ See L10

Initial algebra
an algebra from which there is a unique homomorphism to any other algebra of the same signature. A language’s AST is an initial algebra: there is only one way to interpret it in a given semantic domain.
→ See L11

Interleaving
a concurrency model where “A and B in parallel” means “all possible sequences by alternating actions of A and B”. Used by CCS/CSP.
→ See L12

Invariant
A property of the generated code that must always be true (e.g., no comments in an SC array).
→ See B7, L5

J

Jugalbandi
Indian musical duet where two soloists dialogue and superimpose, each with their own subdivision of time.
→ See B5

K

Kathak
Classical dance of North India, linked to the tabla. Tablist-dancer interactions are a foundational case study for BP3.
→ See B6

Kayda
A tabla composition with a fixed theme (mukhra) and systematic variations. Corresponds to BP3’s SUB1 mode.
→ See B3, B4, B7

Khali
The “empty” (non-resonant) section of an Indian tāla cycle, where dry bols (tin, ta) replace resonant bols (dha, dhin).
→ See B1, B3, M5

Kleene star (*)
Operation on a set that produces all possible strings formed with its elements, including the empty string. If T = {a}, then T* = {ε, a, aa, aaa, …}.
→ See B2

Kleene’s theorem
guarantees that every continuous function on a domain has a least fixed point, obtained as the limit of successive approximations.
→ See L7

L

L-attributed
a class of attribute grammars where inherited attributes depend only on the parent and left siblings. Left-to-right single-pass evaluation, compatible with LL parsing.
→ See L10

Lambda (empty production)
Rule that rewrites a non-terminal to the empty string (ε). The symbol disappears without a trace.
→ See B6

Language
Set of all terminal strings derivable from the start symbol.
→ See B2

LCM
Least Common Multiple — in polymetry, the point where two cycles resynchronize (e.g., LCM of 2 and 3 = 6).
→ See M5

Leftmost (leftmost derivation)
A strategy that always replaces the leftmost non-terminal.
→ See B3

Legato
A connected playing style, where notes follow each other without interruption. Indicated by a slur.
→ See I5

Lexer
A module that transforms raw text into lexical units (tokens). Here, combined with the line classifier.
→ See B7

LHS (Left-Hand Side)
The left part of a production rule, i.e., the symbol being replaced.
→ See B3

LIN (BP3 mode)
Linear mode, where rules are applied cyclically: after the last one, it returns to the first.
→ See B3

Line Classifier
The first pass of the parser that identifies the type of each line (comment, header, mode, preamble, rule) via regular expressions.
→ See B7

Live coding
The practice of modifying code in real-time during execution, facilitated by Pdef in SuperCollider.
→ See B7, M3

Loop Invariant
a logical property true before the loop and preserved by each iteration. Key to proving loop correctness.
→ See L8

LTS (Labeled Transition System): a triplet $(S, \text{Act}, \to)$ — states, actions, transitions. The underlying model of CCS.

Marking

the distribution of tokens in the places of a Petri net. Represents the global state of the system at a given time.
→ See L12

M

Markovian process (memoryless)
A stochastic process where the probability of a future event depends only on the present state, not on the history.
→ See B1

Mathematical function
relation that associates exactly one element from a starting set (domain) with each element from a target set (codomain). Example: f(x) = x + 1 associates each integer with its successor.
→ See L5

Meter
The regular organization of beats into groups with a hierarchy of accents (strong/weak beats).
→ See M5, M6

MIDI Channel
logical subdivision (1-16) allowing different instruments to be addressed on the same cable. Like 16 independent phone lines.
→ See I4

Mildly context-sensitive
Class of languages satisfying Joshi’s criteria: contains CFLs, captures cross-serial dependencies, is semilinear, and allows polynomial parsing.
→ See L9

Monad
mathematical structure allowing the encapsulation of effects (state, randomness, errors) within a functional framework. Used to model programs with side effects in denotational semantics.
→ See L5, L7

Morphing
Gradual transition between two versions of a pattern, made possible by re-evaluating individual Pdefs.
→ See B7

MPE
MIDI Polyphonic Expression. Extension allowing one channel per note for individual expression.
→ See I4

MPR (Metrical Preference Rule)
In GTTM, a preference rule for metrical structure (strong/weak beats).
→ See M4

MPR (Metrical Preference Rules)
Preference rules for metrical structure. They describe how we infer the beat grid.
→ See M6

Music Petri Net
an extension of Petri nets adapted for musical description (Barate, Haus, Ludovico, 2005).
→ See L12

MWSCCS (Musical Weighted Synchronous CCS): an extension of SCCS with stochastic weights for musical composition (Ross, 1995).

Place

a circular node in a Petri net, containing tokens. Represents a state or a condition.
→ See L12

N

· notation
double brackets meaning “the denotation of” or “the mathematical meaning of”. e is read “the denotation of e”.
→ See L5

¬ (negation)
logical connector “not”. ¬P is true if and only if P is false.
→ See L8

Neighbor tone
An ornamental note adjacent to a main note, which moves away by one step and then returns (e.g., C-D-C).
→ See M4

Neighboring tone (embellishment)
An ornamental note that leaves a structural note by conjunct motion and returns to it. Example: C-D-C.
→ See M6

Nesting
a structural property of context-free languages — an element can contain other elements of the same type, to arbitrary depth. This is the key to Type 2.
→ See M2

NLG / NLU (Natural Language Generation / Understanding): The two subfields of NLP (Natural Language Processing) that embody the generation/recognition duality.

Incremental parsing

Syntactic analysis that processes input symbol by symbol, as it is received, without waiting for the end of the sentence. Necessary for real-time analysis. More difficult than offline parsing because the analyzer does not have access to the rest of the signal.
→ See L13

Non-Markovian process (with memory)
A stochastic process where the probability of an event depends on the history of past events.
→ See B1

Non-terminal
An intermediate symbol (variable) that will be replaced during derivation. By convention, written in uppercase (S, NP, VP).
→ See B1, B2, L1, L6

Normalization
A mathematical constraint that the probabilities of a set of mutually exclusive alternatives sum to 1 (100%).
→ See B1

normalizeSum
SC method that divides each element of an array by the total sum, converting weights into probabilities.
→ See B7

Note On/Off
messages indicating the start (Note On) and end (Note Off) of a note.
→ See I4

O

OAG (Ordered Attribute Grammar): an intermediate class between L-attributed and general AG, where a fixed evaluation order can be determined statically for each production. Introduced by Kastens (1980).

Flag (BP3): a named counter with global scope that conditions and modifies the application of grammar rules. Combines the roles of guard (test) and effect (modification).
Multi-pass evaluation

an evaluation strategy where the tree is traversed multiple times, each pass calculating a subset of attributes. Necessary when dependencies do not allow a single pass.
→ See L10

ORD (BP3 mode)
Ordered mode, where rules are applied in the sequential order of the file.
→ See B3

OSI Model
Open Systems Interconnection — a 7-layer model structuring network protocols
→ See M3

Ostinato
A short musical motif stubbornly repeated throughout a passage or piece.
→ See B3

P

Parser
The module that analyzes the syntactic structure of the source code and builds the AST. Here, a two-pass parser (classifier + recursive descent).
→ See B7, L1

Parser (syntactic analyzer)
Program that analyzes a string to determine its grammatical structure.
→ See B2

Parsing (syntactic analysis)
The process that, given a sentence and a grammar, determines if the sentence belongs to the language and reconstructs its structure (derivation tree).
→ See L13

Part
A voice or an instrument in the score.
→ See I5

Partial Correctness
property {P} C {Q} — if C terminates, Q is true. Says nothing about termination.
→ See L8

Partial order (⊑)
“is less defined than” or “has less information than” relation. ⊥ ⊑ x for all x.
→ See L7

Partwise
Organization of the file by instrument then by measure (the most common).
→ See I5

Passing note
A note that connects two structural notes by conjunct motion (e.g., the D between C and E).
→ See M4

Patch / Program / Preset
predefined instrument sound. Program 1 = piano in General MIDI.
→ See I4

Pattern
in SuperCollider or TidalCycles, an object that generates sequences of values according to rules
→ See M3

Pattern matching
Mechanism for matching patterns. BP3 wildcards capture portions of derived strings for reuse.
→ See B6

Pbind
SC pattern that creates a stream of musical events from key-value pairs (instrument, note, duration, etc.).
→ See B7

Pbindf
A variant of Pbind that adds or replaces keys in an existing pattern, without structurally modifying it.
→ See B7

PCFG
Probabilistic Context-Free Grammar — context-free grammar enriched with probabilities (see B1)
→ See M3

PCFG (Probabilistic CFG)
A context-free grammar where each production rule is associated with a probability.
→ See B1

Pdef
A named and reactive container for an SC pattern. Allows live coding and real-time morphing.
→ See B7

Petri Net
a graphical formalism (places, transitions, arcs, tokens) for modeling concurrent systems. Invented by Carl Adam Petri (1962).
→ See L12

Pipeline
A chain of transformations where the output of one stage is the input of the next. Here: BP3 text → tokens → AST → SC code.
→ See B7

Pitch Bend
message continuously varying the pitch of a note (glissando, vibrato).
→ See I4

Poly_ratio
A single-voice polymetric expression {n, seq} compressing or stretching a sequence into n time units. Here, {1, 6 notes} makes 6 notes play in 1 beat — a micro-timing.
→ See M12

Polymetry
superposition of different meters — for example, 3 notes against 2 in the same duration. In BP3, denoted $\{v_1, v_2\}$ .
→ See L12, M5

Polynomial parsing
A syntactic analysis algorithm whose execution time is bounded by a polynomial in the length of the input. For TAGs: O(n⁶). For CFGs (CYK algorithm, Cocke-Younger-Kasami): O(n³).
→ See L9

Polyphony
Superposition of several independent melodic lines. In MusicXML, managed by the <voice> element.
→ See I5

Polyrhythm
A term sometimes synonymous with polymetry, sometimes distinguished (polyrhythm = different accents on the same meter).
→ See M5

Postcondition
property guaranteed after the execution of an instruction.
→ See L5, L8

PPQ
Pulses Per Quarter note. Temporal resolution of a MIDI file. 480 PPQ = 480 ticks per quarter note.
→ See I4

Prand
SC pattern that chooses an element randomly (uniform distribution) from an array, N times.
→ See B7

Precondition
property required before the execution of an instruction.
→ See L5, L8

Preference rule
In GTTM, a rule that indicates a tendency rather than a strict obligation.
→ See M4, M6

Premise
a condition required to apply a rule (above the horizontal bar).
→ See L6

Prime
apostrophe (') indicating “the new value”. σ' = “sigma prime” = new state.
→ See L6

Probabilistic monad
a monad allowing the composition of probability distributions.
→ See L7

Probability distribution
a function associating each possible outcome with its probability. The sum of probabilities is 1.
→ See L7

Process
in process algebra, an entity that performs actions and can interact with other processes. A process is defined by its observable behavior.
→ See L11

PROD (mode)
Production mode of the Bol Processor — the grammar generates musical sequences (modus ponens).
→ See L13

Production rule
An instruction of the form A → x indicating that A can be replaced by x.
→ See B1, B3, L1, M4

Progression (harmonic)
Movement from one chord to another that creates tension and a sense of direction.
→ See M6

Prolongation
A relationship where one musical event extends or elaborates another without creating a new harmonic direction.
→ See M6

Prolonged Rest (UndeterminedRest)
Rest of indefinite duration, noted ... in BP3. Equivalent to a fermata (hold).
→ See B2

Protocol
set of rules defining how two systems communicate.
→ See I4

Prout
SC pattern based on a routine, allowing programmatic control of the flow (conditions, loops, mutable variables).
→ See B7

PRPR (Prolongational Reduction Preference Rules)
Preference rules for prolongational reduction. They describe how we perceive tension/resolution relationships.
→ See M6

Pseq
SC pattern that plays elements of an array in sequence, N times.
→ See B7

Pumping lemma
A proof tool in language theory that demonstrates a language is not context-free.
→ See B6

Pushdown automaton
A finite automaton augmented with a stack (LIFO memory). Can push and pop symbols, which allows it to manage nesting.
→ See L1, M2

Pwrand
SC pattern that chooses an element according to weights (weighted distribution), N times.
→ See B7

R

Rasgueado
A flamenco guitar technique consisting of rapid sweeps across the strings, typically alternating downward (down-strum) and upward (up-strum) movements.
→ See M12

Recursion
The property of a rule that can apply to its own result, allowing for nested structures.
→ See M4

Recursive Descent
A parsing technique where each grammar rule corresponds to a function that recursively calls itself for sub-rules.
→ See B7

Reductional tree
A hierarchical structure where each level simplifies the lower level by retaining only the structurally important elements.
→ See M6

Referential semantics
The ability of language to refer to things in the world (the word “cat” refers to an animal).
→ See M4

Regular expression (regex)
A compact notation for describing text patterns. Equivalent in power to a finite automaton.
→ See L1

Regular language
a language recognizable by a finite automaton (Type 3). Individual MIDI messages form a regular language.
→ See M1

RELAX NG
an XML validation format more expressive than XSD, corresponding to a complete regular tree language. Used by MEI.
→ See M2

Renormalization
Recalculation of probabilities after weight modification. If weights change from [50, 1] to [38, 1], probabilities are recalculated from [98%, 2%] to [97.4%, 2.6%].
→ See B4

Reversible grammar
A grammar designed to be used in both directions (generation and parsing) without transformation. Examples: GF, unification grammars.
→ See L13

RHS (Right-Hand Side)
The right part of a production rule, i.e., what it is replaced by.
→ See B3

Rightmost (rightmost derivation)
A strategy that always replaces the rightmost non-terminal.
→ See B3

RND (BP3 mode)
Random mode, where rules are chosen randomly according to their weights.
→ See B3

Rule
AST node representing a BP3 production rule with grammar number, rule number, weight, flags, LHS, and RHS.
→ See B7

Running status
a MIDI optimization where the status byte can be omitted if it is identical to the previous one. Requires the parser to remember the last status.
→ See M1

S

S-attributed
a class of attribute grammars containing only synthesized attributes. Bottom-up single-pass evaluation, compatible with LR parsing.
→ See L10

Sam
The first beat of the tāla cycle — the point of resolution towards which tihāī and cadences converge.
→ See B3, B5, B6, M5

Sargam
Indian solmization system (Sa Re Ga Ma Pa Dha Ni), equivalent to Western solfège (do re mi fa sol la si).
→ See B5

Saussure, Ferdinand de
Swiss linguist (1857-1913), founder of structural linguistics, known for the concept of the arbitrariness of the sign.
→ See M4

Semantic compositionality
The principle (attributed to Frege) that the meaning of an expression is constructed from the meaning of its parts (“big cat” = meaning(big) + meaning(cat)).
→ See M4

Semantic domain
mathematical set in which programs are interpreted (integers, functions, distributions…).
→ See L5, L7

Semantic rule
an equation or function that defines how to calculate the value of an attribute based on other attributes. Each grammar production is accompanied by its semantic rules.
→ See L10

Semantics
formal study of the meaning of programs.
→ See L5

Semilinearity
Property of a language whose Parikh vectors (counting the occurrences of each symbol) form a semilinear set. Intuitively, word lengths grow regularly.
→ See L9

Shuffle
A ternary rhythm in blues and rock, based on a triplet subdivision.
→ See M5

Small-step
semantics where each transition (denoted →) represents a single execution step.
→ See L6

SMF
Standard MIDI File. MIDI file format (.mid).
→ See I4

SMF (Standard MIDI File): MIDI file format (.mid). Chunk structure (header + tracks).

Status byte

a MIDI byte whose most significant bit is 1 (values 128-255). Identifies the message type and channel.
→ See M1

SOS
Structural Operational Semantics — a formal framework introduced by Plotkin in 1981 to define programming languages.
→ See L6

SpecialFn
AST node representing a BP3 special function (_transpose, _vel, _mm, etc.) with name and arguments.
→ See B7

Staccato
A detached playing style, where each note is played briefly. Indicated by a dot above or below the note.
→ See I5

Start Symbol
The initial non-terminal from which all derivations begin (often S for “Sentence” or “Start”).
→ See B2

State transformer
a function of type State → State. An imperative command is viewed as a state transformer.
→ See L7

Stochastic
Involving a random element. A stochastic process is a process whose evolution depends on chance.
→ See B1, L6, M3

Stochasticity
random or probabilistic nature of a process. A stochastic system can produce different results with each execution.
→ See L5

Strengthening
replacing a precondition with a stronger (more restrictive) condition. If we know that {x > 0} C {Q}, then {x = 5} C {Q} is also valid because x = 5 implies x > 0.
→ See L8

Structural ambiguity
Property of a sentence that admits multiple derivation trees for the same grammar. Frequent in recognition, absent in generation.
→ See L13

Strum
A rapid sweep across guitar strings. A down-strum (D) goes from low to high; an up-strum (U) goes from high to low.
→ See M12

SUB (BP3 mode)
Substitution mode, where all occurrences of the same non-terminal are replaced identically.
→ See B3

SUB1 (BP3 mode)
Substitution 1 mode, where only the first occurrence of a non-terminal is replaced at each step.
→ See B3

Substitution
TAG operation that replaces a marked leaf node (↓) with an initial tree of the corresponding type. Analogous to derivation in a CFG.
→ See L9

Substitution Q[x / e]
an operation that replaces every occurrence of the variable x with the expression e in the formula Q. Example: (x > 3)[x / (x + 1)] = (x + 1 > 3) = (x > 2).
→ See L8

Syntax Tree
A tree-like representation of a derivation, with the starting symbol at the root and terminals at the leaves.
→ See B3

SynthDef
in SuperCollider, a synthesizer definition as a graph of audio generators
→ See M3

Synthesized attribute
an attribute whose value is calculated from the attributes of child nodes. Information flows bottom-up in the tree. Example: the val value of an arithmetic expression node.
→ See L10

Σ (uppercase sigma)
summation symbol. Σwᵢ = w₁ + w₂ + … + wₙ.
→ See L6

T

Tag
An XML syntax element enclosed by < and >, such as <note> or </note>.
→ See I5

TAG (Tree Adjoining Grammar)
Grammatical formalism that manipulates elementary trees (initial and auxiliary) via two operations: substitution and adjunction. Introduced by Joshi (1975).
→ See L9

Tala
Indian rhythmic cycle, structured in groups with specific strokes (e.g., Tintal = 16 beats).
→ See M5

Temporal compression
Playing more notes than time would normally allow, by shortening each note (M < N). Inverse of stretching.
→ See B5

Temporal stretching
Extending notes so they occupy more time than their normal duration (M > N).
→ See B5

Terminal
A final symbol that appears in the output and cannot be rewritten further. By convention, written in lowercase.
→ See B1, B2, L1, L6

Theka
The basic pattern of an Indian tāla, played as an ostinato by the tabla. A fixed sequence of bols that defines the character of the rhythmic cycle.
→ See B1, B2, B3, B7

Tick
smallest unit of time in a MIDI file. The number of ticks per quarter note is defined by the PPQ.
→ See I4

Tie
In musical notation, a connection between two notes of the same pitch to form a single, longer note. Notated note& (start) and &note (end) in BP3.
→ See B5, B7

Tihai
In Indian music, a concluding cadence where a motif is repeated three times, leading to the sam (the first beat of the rhythmic cycle, a point of convergence).
→ See M4, M5

Tihāī
An Indian cadence where a motif is repeated exactly three times to land on sam. Corresponds to BP3’s SUB mode.
→ See B3, B4, B5, B6

Timewise
Organization of the file by measure then by instrument.
→ See I5

Tintāl
The most common tāla (rhythmic cycle) in North Indian classical music: 16 beats in 4 groups of 4.
→ See B1, B3, B7

Token
Basic lexical unit (word, number, operator) recognized by a parser. Corresponds to the grammar’s terminals.
→ See B2

Tonic
The resting note or chord of a tonality (e.g., C in C major), the point of resolution for tensions.
→ See M4

Tonic (I)
The first degree of the scale, a point of rest and harmonic stability.
→ See M6

Top-down parser
A parser that starts from the start symbol and tries to derive the text by applying the rules.
→ See L1

Total Correctness
property [P] C [Q] — C terminates AND Q is true. Combines partial correctness and termination.
→ See L8

Trace
a sequence of observable events produced by a process. The set of traces of a process is the simplest semantic model in CSP.
→ See L11

Transducer
a machine that transforms an input into an output. An FST transforms strings; a tree transducer transforms trees (ASTs). Compilers are tree transducers.
→ See L11

Transition
a rectangular node in a Petri net. Represents an action. Fires when all its input places have enough tokens.
→ See L12, L5

Translational semantics
semantics that defines the meaning of a program by its translation into a target language. The meaning of P is the meaning of T(P) in the target language.
→ See L11

Transpile
to convert code from one language to another at the same level of abstraction
→ See M3

Transpiler
A source-to-source translator between two languages of the same level of abstraction (here, BP3 to SuperCollider).
→ See B7

Tree (computer science)
A hierarchical data structure with a root, intermediate nodes, and leaves. Each node (except the root) has a unique parent.
→ See M6

Tree automaton
a machine that recognizes trees (rather than strings). Used for validating XML documents against a schema.
→ See M2

True concurrency
a concurrency model that distinguishes “A and B simultaneous” from “A then B” or “B then A”. Captured by Petri nets. – $\tau$ (tau): an internal action in CCS, invisible from the outside. Results from synchronization between an action and its co-action.
→ See L12

TSRPR (Time-Span Reduction Preference Rules)
Rules for identifying group heads in time-span reduction.
→ See M6

Tuplet
In Western notation, a group of compressed notes (triplet = 3 notes in the time of 2).
→ See M5

Turing machine
A theoretical model of computation with an infinite tape, a read/write head, and transition rules. Can compute anything that is computable.
→ See L1

Tāla
Rhythmic cycle structuring Indian classical music (e.g., tintāl = 16 beats, jhaptāl = 10 beats).
→ See B2, B5

U

Undetermined Rest
Rest of duration calculated by context, noted _ in BP3. Used in polymetric expressions.
→ See B2

Union (∪)
Set operation that combines two sets. A ∪ B contains all elements of A and all elements of B.
→ See B2

Universal grammar
Chomsky’s hypothesis that all humans are born with innate linguistic principles.
→ See M4

Ursatz
Schenker’s term (German, “original structure”) referring to the fundamental harmonic and melodic skeleton of a tonal piece.
→ See M4

V

Variable
|x| construction whose first occurrence sets a value and subsequent ones replicate it. Allows expressing exact repetition constraints impossible in CFGs.
→ See B6, B7

Variant (termination function)
a positive integer expression that strictly decreases at each iteration of a loop. Its existence proves termination.
→ See L8

Velocity
intensity of a note (0-127), corresponding to the “strike force.” Generally affects volume and/or timbre.
→ See I4, M3

Vibhāg
Section of a tāla. The tintāl has 4 vibhāg of 4 beats each.
→ See B2, B3, B5

Voice
In a polymetric context, an independent stream of notes playing in parallel with other streams.
→ See B5, I5

VST
Virtual Studio Technology. Audio plugin format allowing virtual instruments and effects to be added to a DAW.
→ See I4

Vādi
Dominant note of a raga, the most frequent and important. Its regular presence can be modeled by a BP3 flag.
→ See B4

W

Weakening
replacing a postcondition with a weaker condition (less precise but still correct). If x = 6 is true, then x > 0 is also true: we have weakened the postcondition.
→ See L8

Weakest Precondition (wp)
the least restrictive condition P such that {P} C {Q} is valid. Notation: wp(C, Q). Introduced by Dijkstra (1975).
→ See L8

Wildcard (joker)
?N construction that captures an arbitrary portion of the string. In PROD mode: capture on the left side, re-injection on the right side (context-sensitive rewriting between grammars). In ANAL mode: pattern matching to test membership. Works in both directions — see B8.
→ See B6

Wrap-around
Cyclic behavior where, after reaching the end of a sequence, one returns to the beginning.
→ See B3

X

XML
eXtensible Markup Language — structured text format with nested tags.
→ See I5

XSLT
eXtensible Stylesheet Language Transformations — language for transforming XML into another format.
→ See I5

Ρ

ρ (rho)
Greek letter conventionally used to represent an environment (variable → value dictionary).
→ See L7

Σ

σ (sigma)
Greek letter conventionally used to represent a state (program memory).
→ See L7

Index

Article	Termes
B1	Ambiguity (grammar), Derivation tree (parse tree), Bol, CFG (Context-Free Grammar), Context-free, Derivation, Non-terminal, Normalization, PCFG (Probabilistic CFG), Dynamic weight, Markovian process (memoryless), Non-Markovian process (with memory), Production rule, Khali, Stochastic, Terminal, Theka, Tintāl
B2

Alphabet (V or Σ), Bol** (बोल): Mnemonic syllable of the tabla (e.g., dha, dhin, tin, ta). The “Bol” in “Bol Processor”. Each bol corresponds to a specific stroke producing a distinct timbre.

*String (or word), Empty string (ε), Derivation, Disjoint, Kleene star (), Language, Non-terminal, Parser (syntactic analyzer), Determined Rest, Undetermined Rest, Prolonged Rest (UndeterminedRest), Start Symbol, Theka, Tāla, Terminal, Token, Union (∪), Vibhāg |

| B3 | Syntax Tree, Kayda, Khali, Derivation, Leftmost (leftmost derivation), LHS (Left-Hand Side), LIN (BP3 mode), Derivation Mode, ORD (BP3 mode), Ostinato, Sam, Theka, Tihāī, Tintāl, Vibhāg, RHS (Right-Hand Side), Rightmost (rightmost derivation), RND (BP3 mode), Production Rule, SUB (BP3 mode), SUB1 (BP3 mode), Wrap-around |
| B4 | Ālāp, Categorical (distribution), Configuration (SOS), Āvart, Convergence, Decrement, Flag environment (φ), Flag, Guard, Functional update, Decremental weight, Renormalization, Kayda, Guaranteed termination, Tihāī, Vādi |
| B5 | Aksak, Bol, Temporal compression, Temporal stretching, Hemiola, Jugalbandi, Tie, Sam, Sargam, Additive signature, Tāla, Tihāī, Vibhāg, Voice |
| B6 | Ālāp, Bol, Context-sensitive, Graha bheda, Homomorphism, Kathak, Lambda (empty production), Context marker, Pattern matching, Pumping lemma, Sam, Tihāī, Variable, Wildcard (joker) |
| B7 | AST (Abstract Syntax Tree), BPFile, Line Classifier, Recursive Descent, Emitter, embedInStream, GrammarBlock, Invariant, Lexer, Live coding, Morphing, normalizeSum, Parser, Pbind, Pbindf, Pdef, Pipeline, Prand, Prout, Pseq, Pwrand, Rule, SpecialFn, Transpiler, Bol, Kayda, Theka, Tintāl, Event.silent(dur), HomoApply, \stretch, Tie, Variable |
| I4 | Aftertouch, Bit, BPM, MIDI Channel, Control Change (CC), DAW, Enharmonic, General MIDI (GM), MPE, Note On/Off, Patch / Program / Preset, Pitch Bend, PPQ, Protocol, SMF, Equal Temperament, Tick, Velocity, VST |
| I5 | Alter, Articulation, Tag, Divisions, DOCTYPE, Dynamic, Fifths, HTML, Legato, Part, Partwise, Polyphony, Staccato, Timewise, Voice, XML, XSLT |
| L1 | Finite automaton, Pushdown automaton, Context-free, Regular expression (regex), Grammar, Context-free grammar (CFG), Formal language, Turing machine, Non-terminal, Parser, Bottom-up parser, Top-down parser, Cross-references, Production rule, Terminal |
| L10 | Synthesized attribute, Inherited attribute, Dependency graph, S-attributed, L-attributed, OAG* (Ordered Attribute Grammar*): an intermediate class between L-attributed and general AG, where a fixed evaluation order can be determined statically for each production. Introduced by Kastens (1980).

Flag (BP3): a named counter with global scope that conditions and modifies the application of grammar rules. Combines the roles of guard (test) and effect (modification).
**Multi-pass evaluation, Circularity, Semantic rule |

| L11 | Initial algebra, Bisimulation, CCS* (Calculus of Communicating Systems*): process algebra introduced by Robin Milner (1980). Operators: prefix (a.P), choice (P + Q), parallel (P | Q), restriction ((new a) P).

Parallel composition, Compiler correctness, CSP (Communicating Sequential Processes): process algebra introduced by Tony Hoare (1985). Synchronization on shared events, with three semantic levels (traces, failures, failures-divergences).
**Commutative diagram, Homomorphism, Process, Translational semantics, Trace, Transducer |

| L12 | Action (CCS), Bisimulation, CCS* (Calculus of Communicating Systems*): a process algebra introduced by Robin Milner (1980). Operators: prefix $$a.P$$ , choice $$P + Q$$ , parallel $P \mid Q$ , restriction $P \setminus \{a\}$ .

Parallel composition, CSP (Communicating Sequential Processes): a process algebra by Tony Hoare (1985). Synchronization by shared events, with three semantic models (traces, failures, failures-divergences).
Downbeat, Interleaving, HTSPN (Hierarchical Time Stream Petri Nets): a hierarchical extension of timed Petri nets, used for interactive scores (Senac 1995, Allombert 2007).
Token, LTS (Labeled Transition System): a triplet $(S, \text{Act}, \to)$ — states, actions, transitions. The underlying model of CCS.
Marking, Music Petri Net, MWSCCS (Musical Weighted Synchronous CCS): an extension of SCCS with stochastic weights for musical composition (Ross, 1995).
**Place, Polymetry, Petri Net, Transition, True concurrency |

| L13 | Analysis-by-synthesis, ANAL (mode), Structural ambiguity, Encoder / Decoder, Reversible grammar, IDyOM* (Information Dynamics of Music*): A statistical model of musical prediction based on corpus entropy. Models the listener as an inference machine.

Grammatical inference (grammar induction): The “third direction” — finding the grammar from examples of sentences. The inverse problem of formal language theory.
Modus ponens / modus tollens, NLG / NLU (Natural Language Generation / Understanding): The two subfields of NLP (Natural Language Processing) that embody the generation/recognition duality.
**Incremental parsing, Parsing (syntactic analysis), PROD (mode) |

| L5 | Compositionality, Configuration, Semantic domain, Mathematical function, Invariant, Monad, · notation, Fixed point, Postcondition, Precondition, Inference rule, Semantics, Stochasticity, Domain theory, Transition, Hoare triple |
| L6 | Axiom, Big-step, BNF (Backus-Naur Form), Concatenation, Configuration, Derivation, Non-terminal, Premise, Prime, Cartesian product, Inference rule, Small-step, SOS, Stochastic, Terminal, Σ (uppercase sigma) |
| L7 | Bottom (⊥), Increasing chain, Compositionality, Denotation, Probability distribution, Domain, Semantic domain, Environment, Continuous function, Monad, Probabilistic monad, Partial order (⊑), Fixed point, Kleene’s theorem, State transformer, · (double brackets), ρ (rho), σ (sigma) |
| L8 | Weakening, Assertion, Axiom, Partial Correctness, Total Correctness, Design by Contract, Loop Invariant, Class Invariant, Hoare Logic, Weakest Precondition (wp), Postcondition, Precondition, Strengthening, Substitution Q[x / e], Hoare Triple, Variant (termination function), Formal Verification, ∧ (conjunction), ¬ (negation), ⟹ (implication) |
| L9 | Adjunction, CCG (Combinatory Categorial Grammar), Combinator, Cross-serial dependencies, Fan-out, Mildly context-sensitive, Polynomial parsing, Semilinearity, Substitution, TAG (Tree Adjoining Grammar) |
| M1 | Finite automaton, BNF / EBNF** (Backus-Naur Form / Extended BNF): notation for writing formal grammars. Used to specify the syntax of programming languages. See L3.

Context-free, Data byte, Grammar, Chomsky hierarchy, Regular language, Running status, SMF (Standard MIDI File): MIDI file format (.mid). Chunk structure (header + tracks).
**Status byte |

| M12 | Compas, 3-3-2 Pattern, Poly_ratio, Rasgueado, Strum |
| M2 | Pushdown automaton, Tree automaton, Context-free, DTD* (Document Type Definition*): an older XML validation format, corresponding to a local tree language. Superseded by XSD since MusicXML 4.0.

**Tree grammar, Nesting, RELAX NG |

| M3 | Arpeggio, BP3, DAW, Dataflow, Deterministic, DSL, GTTM, IEEE 1599, Live coding, OSI Model, Pattern, PCFG, Stochastic, SynthDef, Transpile, Velocity |
| M4 | Behaviorism, BP3 (Bol Processor 3), Chomsky, Noam, Neighbor tone, Cadence, Semantic compositionality, Dominant, Frege, Gottlob, GPR (Grouping Preference Rule), Generative grammar, Universal grammar, GTTM (A Generative Theory of Tonal Music), Hierarchy, MPR (Metrical Preference Rule), Passing note, Recursion, Production rule, Preference rule, Saussure, Ferdinand de, Referential semantics, Grouping structure, Tihai, Tonic, Ursatz |
| M5 | Bol, BP3 (Bol Processor 3), Cross-rhythm, Djembe, Downbeat, Dunun, Hemiola, Khali, Meter, LCM, Polymetry, Polyrhythm, Sam, Shuffle, Tala, Tihai, Tuplet |
| M6 | Tree (computer science), Reductional tree, Neighboring tone (embellishment), Cadence, Consonance/Dissonance, Dominant (V), Elaboration, GPR (Grouping Preference Rules), GTTM (Generative Theory of Tonal Music), Meter, Conjunct motion, MPR (Metrical Preference Rules), PRPR (Prolongational Reduction Preference Rules), Progression (harmonic), Prolongation, Preference rule, Head, Tonic (I), TSRPR (Time-Span Reduction Preference Rules) |