Glossary of Formal Languages & Compilation

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

A

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

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

$\omega$ exponent of matrix multiplication, $\le 2.371552$ (Williams et al. 2024). Bounds CFG parsing via Valiant. → See L17

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

$T_{\text{gen}}$ , $T_{\text{parse}}$ Time complexity functions for generation and recognition respectively, parameterized by Chomsky level $k$ and length $n$ . → See L15

/N and \N Primitive speed operators of BP3. /N multiplies speed by N (accelerates), \N divides it by N (slows down). N must be a positive integer. Inherited from BP1/BP2. In the C code: T0 with sub-type 11 (/) or 25 (\). → See B12

3-3-2 Pattern 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

*N and **N Scaling operators of BP3. *N multiplies scaling by N, **N divides it by N. N must be a positive integer. In the C code: T0 with sub-type 21 (*) or 24 (**). → See B12

_tempo() Special function of BP3 (T43 in the C code) that modifies the local tempo by a rational factor x/y. Unifies /N (speed) and *N (scaling) into a single command: speed *= x, scaling *= y. → See B12

AC Algorithmic Composition — an approach where software assists the composer with algorithms, without replacing their decisions. Lineage: Common Music → OpenMusic → PWGL → Opusmodus → See M7

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

Actor A binding unit that links an alphabet, a scale, sounds, a transport, and an evaluator — the complete resolution context of a symbol → See S3, S9

ActorDirective Node declaring an actor with its properties (alphabet, scale, sounds, transport…) → See S13

Adapter A program that translates timestamped BPscript events into commands for a runtime → See S4

Adjunction The central operation of TAGs. It 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

Almost minimal finite automaton A compact representation of a regular language built by QAVAID (separate Prolog II program) from examples. “Almost” minimal because exact minimization can over-generalize. → See B8

Alphabet Ordered sequence of note names + available alterations — purely nominal → See S9

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) Property of a grammar where the same string can be derived in several different ways (multiple possible syntax trees). → See B1

ANAL (mode) BP3’s analytical mode — the grammar tests if a sequence belongs to the language. Uses template matching and wildcards. Corresponds to modus tollens. → See B8, L13

Analysis-by-synthesis A paradigm where recognition uses generation as an internal subprocess. The receiver generates hypotheses and compares them to the received signal (cf. L13). → See B8, L13

Aroha/Avaroha Ascending/descending scale of an Indian raga — can be different → See S9

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

ARROW Type of arrow in a BP3 rule (-->, <->, <--). Determines in which directions (PROD, ANAL) the rule is active. → See B10

Articulation Indication of how a note should 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 — tree representation of a program after parsing → See B11, S13

Axiom an inference rule without premises (conclusion always true). Example: $\langle n \rangle \Downarrow n$ is an axiom because a number always evaluates to itself. → See L6, L8

Ālāp Slow introduction of a raga in Indian music, without a fixed pulsation, where the musician progressively explores the notes of the mode. → See B12, B4, B6, S5, S6

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

B

Backtick the ` character used in BPscript to delimit native code intended for a runtime → See S1, S4

Backtracking Algorithmic technique of backtracking when a partial solution fails → See B13

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

Best known algorithm bound ceiling reached by the best algorithm published to date; can be improved. → See L17

Bidirectional capable of generating and recognizing; see L13 → See S1

Bidirectionality Property of a grammatical formalism that can be used for both generation (producing strings) and recognition (analyzing strings) with the same grammar. → See L16

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

Binding A link between a symbol and its actor — implicit (inferred) or explicit (dot notation) → See S3

Birman-Ullman (paradox) The observation that transforming a parser into a generator is easy, while transforming a grammar into a parser is difficult — seemingly the inverse of asymmetry, but in reality its confirmation. → See L15

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 the syntax of a language. 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 Mnemonic syllable of the Indian tabla (e.g., dha, dhin, tin, ta). The “Bol” in “Bol Processor.” → See B1, B6, M5

Bol Processor (BP3) a system of formal grammars for music, developed by Bernard Bel since 1989, initially for the North Indian tabla → See S1

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 ( $\bot$ ) minimal element of a domain, representing absence of information or non-termination. Pronounced “bottom”. Example: an infinite loop has $\bot$ as its denotation. → See L7

Bottom-up A parsing strategy that starts from the terminal symbols (the leaves of the tree) and ascends towards the axiom (the root). Examples: LR, CYK. → See L14

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

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

Buffer current events continue to play while the new sequence is being calculated → See S11

C

Cadence A chord progression that punctuates the end of a musical phrase (e.g., $V \to I$ = dominant → tonic). → See M4, M6

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

Cascade Priority system between layers — the most specific layer overrides the others → See S14

Catalan (numbers) The sequence $C_n = \frac{1}{n+1}\binom{2n}{n}$ which counts the number of binary trees with $n$ nodes. Exponential growth $\sim 4^n / n^{3/2}\sqrt{\pi}$ . → See L15

Catalan numbers $C_n \sim 4^n/n^{3/2}\sqrt\pi$ —count the derivation trees of an ambiguous CFG string. → See L17

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

Causal (system) In signal processing, a system whose output at time $t$ depends only on inputs at times $\leq t$ . The generator is causal; a parser without lookahead is also. → See L15

CCG (Combinatory Categorial Grammar) A grammatical formalism where each word carries a typed category (like $(S\backslash NP)/NP$ for a transitive verb) and words combine through 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

Cents Logarithmic unit — 1200 cents = 1 octave, 100 cents = 1 semitone in 12-TET → See S15, S9

CFG (Context-Free Grammar) A grammar where each rule replaces a single non-terminal symbol, regardless 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 1928), founder of the theory of generative grammars. → See M4

Chomsky-Shannon-Morris Triptych Three complementary theoretical frameworks for understanding BP3’s modes. Chomsky = structural complexity (hierarchy), Shannon = encoding/decoding (direction), Morris = cycle correctness (commutativity). → See B8

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

Coarticulation In phonetics, the modification of a sound by its adjacent sounds. By analogy, BP3’s time-setting modifies the phrasing of a sound-object based on its temporal context. → See B9

Combinator A 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

Communicative efficiency pressure shaping languages toward a speaker-effort / informativeness trade-off. → See L21

Compas Rhythmic cycle in 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: Morris’s diagram commutes. → See L11

Compositional path Sequence of flag states that defines a trajectory through the grammar — each state activates a different set of rules → See S6

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

Compression rate ( $R$ ) number of signifiers (bits) per transmitted signified. Compressing = lowering $R$ = spending less energy $E(R)$ . → See L21

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). Noted $\langle e, \sigma \rangle$ where $e$ is the expression and $\sigma$ is the state. → See L5, L6

Configuration (SOS) Tuple representing the complete state of the system during derivation. For BP3 with flags and weights: $(\sigma, \varphi, 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

Constraint-satisfaction Problem of finding values that satisfy a set of constraints → See B13

Context a condition for rule application, based on neighboring symbols — positive (A B) or negative #(A B) — tested during derivation, never modified → See S8

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

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

Context-free grammar (CFG) A grammar where all rules are of the form $A \to \gamma$ (a single non-terminal on the left). → See L1

Context-sensitive A property of a grammar where the replacement of a symbol depends on its environment. Corresponds to Type 1 of the Chomsky hierarchy. → See B6, S8

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

Control BP3 control written directly in the stream (vel(120), goto(2,1)) → See S13

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

controlTable Table {CTn → parameters} — runtime () compiled into _script(CTn) → See S10

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 A syntactic structure where two sequences of elements correspond element by element, like subjects and verbs in Dutch ( $A_1\ A_2\ A_3\ B_1\ B_2\ B_3$ where $A_i$ depends on $B_i$ ). → See L9

Csound Sound synthesis language created by Barry Vercoe (MIT, 1986). BP3 can generate Csound code as an alternative to MIDI, allowing arbitrarily complex grammar terminals. → See B9

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

CT (Control Table) Point-in-time override via () — persists until the next () → See S14

CV (Control Voltage) Continuous modulation over a duration (ADSR, LFO, ramp) — declared cv name : mod.type(args), bound per note (input: name) → See S14, S3

CV engine Downstream component that resolves CV objects (ADSR, LFO, ramp) into audio buses or CC messages → See S10

CVInstance Declaration of a CV object at the top of the scene (envelope, LFO, ramp) → See S13

CYK (Cocke-Younger-Kasami): A bottom-up parsing algorithm using dynamic programming. Runs in $\mathcal{O}(n^3)$ for any CFG.

Top-down A strategy that starts from the axiom (the root) and descends towards the terminals (the leaves). This is the natural direction of generation. In parsing, this is the LL strategy. → See L14

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, M7

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

DCG (Definite Clause Grammar): Grammatical extension of Prolog, inherently bidirectional thanks to unification, but with asymmetrical pathologies (different infinite recursions in each direction).

Declarativity Property of a grammar that separates what it says (linguistic content) from how it is processed (direction, traversal strategy). A prerequisite for bidirectionality according to Appelt. → See L16

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

Degree shift changing the starting degree in the scale — produces a different mode → See S15

Denotation the mathematical value (function, set, etc.) associated with an expression. Noted $\llbracket e \rrbracket$ 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 Sequence of rule applications starting from the initial symbol (S) to a string containing only terminals. → See B1, B2, B3, L6, S1, S2

Derivation mode In BP3, a sub-grammar strategy for choosing and applying rules (ORD, RND, LIN, SUB, SUB1, TEM, POSLONG). → See B3, S5

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

DERIVATION_MODE Traversal direction for an individual rule (LEFT, RIGHT, RND). Distinct from the block’s MODE. → See B10

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

Desirable difficulty (desirable difficulties, R. & E. Bjork): observation that well-calibrated learning obstacles improve retention—the empirical idea of a non-trivial error optimum.

Striatum / basal ganglia brain structures (modulated by dopamine) that calculate effort cost and form habits. → See L21

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

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

Differential coupling generation and recognition are sensitive to both axes (class × sub-problem), but with an inverted primary sensitivity. → See L17

Directive an @… instruction that configures the entire scene, outside the temporal flow → See S2

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

Distributed Composition Architecture where multiple BPscript instances on different machines synchronize via triggers → See S7

Divisions Number of subdivisions per quarter note, defines the file’s temporal resolution. → 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 ( $\sqsubseteq$ ) and completeness properties; serves as a “value space” for programs. → See L7

Domain theory branch of mathematics providing the structures (ordered domains) necessary 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) Fifth degree of the scale, a tension chord that calls for the tonic. → See M6

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

Dragon Book Nickname for Compilers: Principles, Techniques, and Tools (Aho, Sethi & Ullman, 1986), the reference book in compiler design. → See L14

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

DTD (Document Type Definition): 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 Family of cylindrical double-headed drums (dununba, sangban, kenkeni) playing patterns in West Africa. → See M5

Dynamic Tonality Parametric temperament whose generator can vary continuously → See S9

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

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

E

Earley A hybrid (top-down-bottom-up) parsing algorithm capable of processing any CFG in $\mathcal{O}(n^3)$ . → See L14

EBNF Extended Backus-Naur Form — standard notation for syntax (ISO 14977) → See S12

EBNFdoc Systematic documentation format for EBNF productions, inspired by API references (Javadoc, MDN). Each production is documented with its typed components, constraints, C source, and examples. → See B10

Ecological oracle here, the non-formal oracle formed by interaction feedback (repair, alignment, desynchronization), primarily implicit. → See L21

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

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

Encoder Step 3 — translates the AST into BP3 grammar + emits the terminalActorMap and prototypes → See S10

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

ENGINE_KEY Reserved key for engine qualifiers [] → See S12

Enharmonic equivalence Equivalence between two notations of the same frequency (C# = Db) — only exists in equal temperament → See S15

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

Entrainment synchronization of rhythmic behaviors between interacting individuals (here, in joint music). → See L21

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

Error rate / distortion ( $\varepsilon$ ) proportion of what the receiver does not correctly reconstruct. Increases with compression $R$ , decreases with shared knowledge $\kappa$ . → See L21

Extracted learning ( $G$ ) knowledge gain $d\kappa$ derived from resolved errors. Function of $\varepsilon$ in an inverted U (neither too little nor too much) and the power of the oracle. → See L21

F

Fan-out A 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^2$ , because $f(0) = 0$ . In semantics, used to define loops and recursion. → See L5, L7

Flag Conditional variable attached to a rule (/name=value/). Controls activation and modifies the derivation state. → See B10, B4, S1, S2, S6

Flag environment ( $\varphi$ ) Function that associates each flag name with its current integer value. Notation: $\varphi(\text{avart}) = 4$ . → See B4

Flat alphabet Convention where terminals are opaque names prefixed with bol — BP3 does not know what they mean → See S10

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

FST (Finite-State Transducer): A finite-state automaton with input and output. The inverse of an FST is also an FST—a property that does not generalize to context-free grammars.

GF (Grammatical Framework): Multilingual grammatical formalism by Ranta (2004, 2019) with abstract/concrete syntax separation, allowing parsing and generation in 40+ languages.
Grammar Inversion Strzalkowski’s technique for automatically transforming a parsing grammar into a generation grammar by inverting the control structure. Proves that direction is embedded in procedural grammars. → See L16

Function (gen) vs relation (parse) Generation is a function (single-valued): its input — (grammar + derivation) — determines the output. This is not injectivity (two derivations can yield the same string). Parsing is a relation (one sentence → multiple trees) because its input — (grammar + string) — is less informative and underdetermines the tree. → See L15

Functional update Operation that creates a new environment identical to the old one except for one variable. Notation: $\varphi[\text{avart} \mapsto 3]$ means ” $\varphi$ with avart changed to $3$ .” → See B4

G

Gate A signal that remains active for a duration — in BPscript, a symbol that occupies time → See S3

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

Generation under semantic constraint producing a string that additionally satisfies an external constraint. NP-complete from $k=2$ with features (Brew 1992). → See L17

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. Describe how we perceive boundaries between musical groups. → See M6

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

Grain In granular synthesis, a micro-sound fragment (typically 1-100 ms) which, combined with thousands of others, forms complex textures and sounds. → See B9

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

grammar_section Grammar block containing a mode, an optional preamble, and rules. → See B10

Grid shift transposition by shifting N steps in the temperament grid — only works in equal temperament → See S15

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 at most $\lceil N/M \rceil + 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, S2, S6

H

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

Hemiola Specific polymeter where 2 and 3 are superimposed (6 beats = 2x3 = 3x2). → See 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 Homomorphism node — MASTER (=X) defines, SLAVE (:X) replicates → See B11

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

Hot-swap Hot-swapping — modifying code while the system is running, without stopping it → See S11

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

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 6-layer synchronized XML musical representation → See M3

Implicit resolution The compiler infers the actor of a symbol when there is no ambiguity → See S3

Incoming Trigger (<!) Synchronization point — the derivation waits for an external signal → See S7

Increasing chain a sequence of elements $x_0 \sqsubseteq x_1 \sqsubseteq x_2 \sqsubseteq \ldots$ where each element has “more information” than the previous one. Used to construct fixed points. → See L7

Indeterminate rest Rest with a duration calculated by the context, noted as _ in BP3. Used in polymetric expressions. → See B2, S5

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

Informant regime (vs. text): in Gold, learning with access to answers/counter-examples, more powerful than positive data alone.

Superfinite class class containing all finite languages and at least one infinite one; not identifiable from positives alone (Gold’s wall). → See L21

Information bottleneck formal framework (Tishby) for the trade-off between compressing a variable and information retained about another—candidate for formalizing $\varepsilon^{*}$ . → See L21

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

Inherited attribute ( $\downarrow$ ): Information that descends from parent to child in an attribute grammar. Top-down flow.

Synthesized attribute ( $\uparrow$ ): Information that ascends from child to parent in an attribute grammar. Bottom-up flow.
Chart (parsing table) A tabular data structure used by parsing algorithms (Earley, CYK, chart parsing) to store intermediate results. In parsing, indexed by positions in the input string. In generation, this indexing is impossible (the string does not yet exist), hence the need to be driven by semantic heads. → See L14

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

Inline backtick A backtick within a symbol call — the runtime is inferred from the symbol, no tag needed → See S4

Input object A zero-duration time-object that waits for an external signal (MIDI note, mouse click) to synchronize real-time performance. → See B9

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

Intrinsic ambiguity A property of a language (not a grammar) such that every grammar that generates it is ambiguous. Discovered by Parikh (1966). → See L15

Intrinsic bound characterization of the difficulty of the problem itself ( $\Theta(f)$ or complexity class), which no algorithm can beat unless a conjecture is overturned. → See L17

Invariant property that remains true throughout execution. → See L5

Inverse Folding In bioinformatics, the problem of designing an RNA sequence that folds into a target structure. NP-hard (Bonnet et al., 2020). → See L16

IR Intermediate Representation — intermediate representation between source and target → See B11

J

Jhālā Concluding phase of a raga, fast and virtuosic → See S6

JIT Just-In-Time compilation — compilation of code at runtime. Extempore uses LLVM JIT to compile DSP live → See M7

Jor Intermediate phase of a raga, progressively rhythmic → See S6

K

K-parameter Interactive weight (<K1>, <K1=5>) allowing the user to dynamically control rule selection. → See B10

KAMP Appelt’s system unifying planning and realization in NLG. Bidirectional but “computationally impracticable.” → See L16

Kathak Classical dance of Northern India, linked to the tabla. Tabla player-dancer interactions are a founding case study for BP3. → See B6

Kayda Tabla composition with a fixed theme (mukhra) and systematic variations. Uses complex grammatical structures (sub-grammars, templates), not simply SUB1 mode. → See B3, B4, B8

Khali “Empty” section (without resonance) 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, b, aa, ab, ba, bb, aaa, …}. → See B2

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

Knowledge gradient ( $\kappa$ ) amount of grammatical knowledge available, from 1 (known grammar, recognition) to 0 (nothing known, pure inference). → See L21

Kpress Compression factor of the phase diagram in PolyMake(). Reduces temporal resolution when the grid exceeds memory limits. → See B12

L

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

Lambda Empty production (ε) — the non-terminal disappears → See B11

Lambda (empty production) A rule that rewrites a non-terminal as the empty string ( $\varepsilon$ ). 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 polymeter, the point where two cycles resynchronize (e.g., LCM of 2 and 3 = 6). → See M5, S5

Learning progress speed at which one learns ( $\approx d\kappa/dt$ ); models curiosity as intrinsic utility (Gottlieb & Oudeyer). → See L21

Left-corner A hybrid parsing strategy that starts bottom-up (the first symbol) then continues top-down (prediction). → See L14

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

Leftmost derivation Derivation strategy that always rewrites the leftmost non-terminal in the work string. In BP3’s LIN mode, the choice among applicable rules at this position is random. → See B3

Legato Connected playing style, where notes flow into each other without interruption. Indicated by a slur. → See I5

LHS (Left-Hand Side) Left side of a rule — what is rewritten. Must contain at least one element. → See B10, B3

LIN (BP3 mode) Linear mode — the candidate rule is chosen randomly from those that produce a leftmost derivation (the leftmost non-terminal is rewritten first). → See B3

Live coding a performative programming practice where code is written and modified in real-time in front of an audience → See M3, M7, S11, S2

LL (Left-to-right, Leftmost derivation): Predictive top-down parsing. Mimics the direction of generation. Less powerful than LR.

Lookahead Number of lookahead symbols a parser consults to decide which rule to apply. Noted as $k$ in LL( $k$ ) and LR( $k$ ). → See L14

Loop invariant a logical property true before the loop and preserved by each iteration. Key to correctness proofs for loops. → 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

Macro textual substitution — the compiler replaces the call with the macro’s body before any analysis → See S2

Markovian process (memoryless) 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) to each element of an arrival set (codomain). Example: $f(x) = x + 1$ associates each integer with its successor. → See L5

MCSL Mildly Context-Sensitive Language — a class of languages between context-free (Type 2) and context-sensitive (Type 1) → See M7

MCSL (Mildly Context-Sensitive Languages) Class of languages between Type 2 (context-free) and Type 1 (context-sensitive). Position of grammars written within BP3. → See B10

MDL (Minimum Description Length): criterion for choosing a model; the best one minimizes (model size) + (data encoded by it). Quantified Occam.

CRC (cyclic redundancy check): redundant bits added to detect corruption. Removing them compresses but reduces robustness.
Under-specification omitting, in a message, what the receiver can reconstruct—compressing at the source. → See L21

Membership decision determining if a string belongs to the language (yes/no)—the reference bound on the recognition side. → See L17

Membership test The decision problem: “does this sequence belong to the language generated by this grammar?”. In BP3, solved by template matching in ANAL mode. → See B8

Meter Regular organization of beats into groups with a hierarchy of accents (strong/weak beats). → See M5

Metric Hierarchical organization of strong and weak beats, distinct from rhythm (note durations). → See M6

Metric properties Characteristics of a sound-object related to its internal duration and how its timing adjusts to tempo. → See B9

Microsound Curtis Roads’ term for the temporal scale of grains (below the note, above the sample). → See B9

MIDI Musical Instrument Digital Communication — universal protocol (1983) for transmitting musical events between instruments and software. MIDI 2.0 (2020) extends resolution to 32 bits → See M7

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 A class of languages satisfying Joshi’s criteria: contains CFLs, captures cross-serial dependencies, is semilinear, and allows polynomial parsing. → See L9

Mini-notation TidalCycles’ compact syntax for describing rhythmic patterns within quotes → See M7

MODE Derivation mode of a grammar block (ORD, RND, LIN, SUB, SUB1, TEM, POSLONG). Determines the rule selection strategy. → See B10

Model surprise (Bayesian) magnitude of model change after an event = information gained about the grammar. In bits. → See L21

Modular power BP3 is not fixed to a Chomsky class — depending on the activated mechanisms, it ranges from context-free (Type 2) to context-sensitive (Type 1), or even beyond; see B6 → See S1

Modus ponens Direct logical reasoning: “if A implies B, and A is true, then B is true”. In BP3: if the grammar has the rule S → A B, we can produce A B. Direction: PROD. → See B8

Modus tollens Inverse logical reasoning: “if A implies B, and B is false, then A is false”. In BP3: if a sequence does not correspond to any derivation of the grammar, it is not grammatical. Direction: ANAL. → See B8

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

Morris Diagram Commutative diagram (Morris, 1973) that formalizes compiler correctness: the result must be the same whether one takes the “compile then execute” path or “interpret directly”. Applied to the PROD→ANAL→adjusted weights→re-PROD cycle. → See B8

MOS (Moment of Symmetry) Scale generated by a single interval (generator) reduced within a period → See S9

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. Describe how we infer the beat grid. → See M6

Music engraving the process of laying out a score according to professional typographic conventions. LilyPond automates this process → See M7

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

MusicXML standardized XML exchange format (W3C) for digital scores. Interoperability between Finale, Sibelius, MuseScore, LilyPond → See M7

Mutation Modification of a flag via [flag=value], [flag+1] or [flag-1] at the end of the rule — applied when the rule is triggered (out-of-time), not at a point in the played flow → See S6

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

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

Neighboring tone (embellishment) 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 an arbitrary depth. This is the key to Type 2. → See M2

NLG / NLU (Natural Language Generation / Understanding): The two sub-domains 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

NLG (Natural Language Generation): Sub-field of NLP concerning text generation. The Reiter & Dale pipeline decomposes the process into document planning → microplanning → surface realization.

NLG Pipeline Three-stage architecture (Reiter & Dale, 2000): 1) document planning (what to say), 2) microplanning (how to say it), 3) surface realization (the sentence). Structurally top-down. → See L16

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

NonTerminal A symbol that can be rewritten (starts with an uppercase letter in BP3) → See B11

Normalization Adjustment of durations so that all voices have the same total duration → See B13, B1

Notation $\llbracket \cdot \rrbracket$ double brackets meaning “the denotation of” or “the mathematical meaning of”. $\llbracket e \rrbracket$ is read “the denotation of $e$ ”. → See L5

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 statically determined for each production. Introduced by Kastens (1980).

Flag (BP3): a named global-scope counter 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

Octaves Register naming convention (position, separator, low→high list) → See S9

on_fail Failure management directive — what to do when no rule applies (skip, retry, fallback) → See S6

Optimal error rate ( $\varepsilon^{*}$ ) error rate that maximizes learning per unit of energy. Distinct from the communicative optimum (which minimizes error). → See L21

Oracle In the context of grammatical inference, the expert (the musician) who validates or rejects generalizations proposed by the system. → See B8, L21

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

Orphan backtick A backtick at the top of the scene, not attached to a symbol, executed at init — requires a runtime tag → See S4

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

Out-time object <<...>> element played immediately, outside the normal temporal flow. Can be a MIDI note or a sound-object. → See B10, B9

Outgoing Trigger (!) Signal sent to a runtime at the time of execution → See S7

OutTimeObject Out-of-time object <<symbol>> — triggered without occupying duration → See B11

P

P-chain psycholinguistic framework (Dell & Chang) where prediction links production, comprehension, and acquisition; prediction error drives learning. → See L21

Parser A program that analyzes text according to a grammar and builds a structure (syntax tree). → See L1, S10

Parser (syntax 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 whether the sentence belongs to the language and reconstructs its structure (derivation tree). → See L13

Part A voice or 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 ( $\sqsubseteq$ ) relation “is less defined than” or “has less information than”. $\bot \sqsubseteq x$ for all $x$ . → See L7

Partwise File organization by instrument then by measure (most common). → See I5

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

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

Patching Wiring of audio modules (filter → reverb → output) — managed by the runtime, not by BPscript → See S14

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

Pattern matching A mechanism for matching motifs. BP3 wildcards capture portions of derived strings for reuse. → See B6

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

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

Performance control Special function (_name(args)) controlling sound rendering (pitch, velocity, timing, etc.). 68 functions defined in BP3. → See B10

Periodic notation notation using . to divide a sequence into fragments of equal symbolic duration → See S5

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

Phase diagram Internal data structure of BP3 (Maxconc × Maxevent grid) representing the temporal placement of all events after polymetric expansion. → See B12

Pitch Bend message that continuously varies 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} plays 6 notes in 1 beat — a micro-timing. → See M12

PolyMake() C function in Polymetric.c that implements polymetric expansion. Not formally documented. → See B13

Polymeter Superposition of several different meters (e.g., 3 against 4). → See M5

Polymetric expansion Transformation of {v1, v2} into a sequence of timestamped events → See B13

Polymetric ratio The N in {N, ...}. Defines how many beats the sequence occupies. It is not a tempo operator (no speed modification), it is a structural ratio with local scope. Accepts rationals ({3/2, ...}). → See B12, S5

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

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

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

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

POSLONG (BP3 mode) Position + Longest mode, a variant of SUB1 that selects the longest derivation among candidate rules at the leftmost position. Leftmost-longest match strategy. → See B3

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

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

Predictive coding / free energy principle (Friston) according to which the brain minimizes surprise (prediction error). → See L21

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

Primary The element before ! — must occupy time (gate, cv, or silence) → See S7

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

Process with memory Stochastic process where the probability of an event depends on the history. BP3 with dynamic weights is technically extended-state Markovian (counters are part of the state), but the observable behavior is memory-based. → See B1

Prod LCM (least common multiple) of all duration ratios in a piece. Determines the resolution of the integer grid of the phase diagram. → See B12

PROD (mode) BP3’s production mode — the grammar generates musical sequences by derivation. Corresponds to modus ponens. → See B8, L13

Production rule Instruction of the form $A \to 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 Relationship where a musical event extends or elaborates another without creating a new harmonic direction. → See M6, S5

Prolonged rest (UndeterminedRest) Silence of indefinite duration, noted as ... in BP3. Equivalent to a fermata. → See B2

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

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

PSPACE-complete A class of problems solvable in polynomial space but for which no polynomial-time algorithm is known. Parsing context-sensitive grammars is PSPACE-complete. → See L15, L17

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

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

Q

QAVAID (Question Answer Validated Analytical Inference Device): Separate Prolog II program (1988-1990) for interactive grammatical inference, developed by Bel & Kippen. Never integrated into BP3, abandoned. The name also means “grammar” (قواعد) in Arabic/Urdu.

Round-trip test A validation test where sequences produced by an inferred grammar are submitted to the musician who provided the original examples. If accepted, the grammar has captured the tacit rules. Musical equivalent of Morris’s commutativity test. → See B8

Qualifier Qualifier [] for the BP3 engine (speed, weight, tempo…) → See S13

Quantization aligning changes to a time grid — the change takes effect at the next beat or cycle → See S11

R

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

Rate-distortion theory (Shannon) of the minimum number of bits to transmit a message at a given fidelity. Tolerating a little loss allows for more compression. → See L21

raw_value Raw value (any text up to , or ]) for engine keys → See S12

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

Reductional tree Hierarchical structure where each level simplifies the lower level by keeping only the structurally important elements. → See M6

Referential semantics The ability of language to talk about 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

REPL Read-Eval-Print Loop — an interactive console that maintains state between commands → See S4

Reserved Word a word that the language reserves for itself — the user cannot redefine it or use it as a name → See S2

Resolver Downstream component (1 per actor) that translates token → frequency via the 5 pitch layers → See S10, S3, S9

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

Reward prediction error gap between expected and received reward, signaled by dopamine (Schultz); neural substrate of surprisal and update. → See L21

RHS (Right-Hand Side) Right side of a rule — the result of rewriting. Can be empty (ε-production). 23 possible element types. → See B10, B3

RHSElement Union type of the 19 node types that can appear on the right-hand side of a rule → See B11

Rightmost (right derivation) 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_prefix Unique identifier of a rule (gram#N[M]). N = block index, M = rule index within the block. → See B10

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

Runtime an execution environment that consumes the timestamped sequence produced by the engine (downstream layer) → See S1, S2, S4

RuntimeQualifier Qualifier () for the runtime (vel, pan, wave…) — compiled into _script(CTn) → See S13

S

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

Sam First beat of the tāla cycle — the point of resolution for Indian cadences. → See B3, B6, M5

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

Scaling Internal variable of PolyMake() which, combined with speed, determines the effective tempo (speed/scaling). Modified by *N, **N and the denominator of _tempo(x/y). → See B12

Scope The visibility area of a variable — each runtime has its own, isolated from others → See S4

Secondary The symbol after ! — triggers at the same instant as the primary → See S7

Semantic compositionality Principle (attributed to Frege) according to which 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 A property of a language whose Parikh vectors (counting the occurrences of each symbol) form a semilinear set. Intuitively, word lengths grow in a regular manner. → See L9

Session View Ableton Live’s grid view where clips are launched freely, without a timeline → See S11

Shared derivation forest A data structure that compactly represents (in $\mathcal{O}(n^3)$ ) an exponentially large number of derivation trees. Non-determinism is compressed, not eliminated. → See L15

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

Sign reversal for constrained generation, the asymmetry reverses—generating becomes harder than analyzing. → See L17

Simultaneous Group a set of events attached to the same instant, often factorized into a macro → See S7

SimultaneousGroup AST node for Sa!dha!spotlight (primary + secondary, temporal) → See S12

Small-step semantics where each transition (denoted $\to$ ) represents a single step of execution. → 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

Smooth time Temporal mode of BP3 (_smooth) where durations are intrinsic properties of objects, without reference to a pulsation. Implements Boulez’s “smooth time”. → See B12, S5

SOS Structural Operational Semantics — formal framework introduced by Plotkin in 1981 for defining programming languages. → See L6

Sound-object Musical entity with metric and topological properties, more general than a note → See B13, B9

Spec Permanent properties of a terminal (timbre, sample, decay) — resolved once at loading → See S14

SpecialFn BP3 special function (_tempo, _smooth, _legato, etc.) — 30+ functions → See B11

Speed Internal variable of PolyMake() representing the current speed of the stream. Modified by /N, \N and the numerator of _tempo(x/y). → See B12

SpeedRatio Speed/scale operator (/2, *3, **3, \2) → See B11

Spines in Humdrum, vertical columns of a **kern file, each representing a voice or a musical dimension → See M7

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

Standalone backtick A backtick in the flow of a rule, executed at the moment of derivation — requires a runtime tag → See S4

Start symbol The initial non-terminal from which all derivation begins (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

Step An elementary interval in the temperament grid → See S15

Stochastic Involving a random element. A stochastic process is one 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

Striated time Concept from Boulez (1963) designating a temporal flow divided by regular reference points (pulsation, measure). Default mode of BP3 (_striated). → See B12, S5

Strongly-timed ChucK’s paradigm where time is a native type of the language, manipulable like any other data → See M7

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

Structural Symbol a character (or group of characters) with a fixed syntactic meaning → See S2

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 — parallel derivation where all candidate rules apply simultaneously to the work string, as in L-systems. → See B3

SUB1 (BP3 mode) Substitution 1 mode — a single pass of rewriting, leftmost, deterministic. Rules are tested in file order. → See B3

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

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

Surprisal $S(w_i) = -\log_2 P(w_i | w_1 \ldots w_{i-1})$ . Measures the information contributed by a token in context. Zero for the generator, positive for the parser. → See L15

Surprisal (predictive surprise) $-\log_2$ of the probability an event had under the current model. In bits. Measurable without knowing the true grammar. → See L21

Symbolic time Representation of time in BP3 in the form of rational fractions (Q), independent of physical milliseconds. → See B12

SymbolWithTriggerIn AST node for Sa<!sync (symbol + attached incoming trigger) → See S12, S13

Sync tag Synchronization point <<WN>> between polymetric voices. Rendezvous mechanism. → See B10

Syntax tree Tree-like representation of a derivation, with the start 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 of an arithmetic expression node. → See L10

Σ (capital sigma) summation symbol. $\Sigma w_i = w_1 + w_2 + \ldots + w_n$ . → See L6

T

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

TAG (Tree Adjoining Grammar) A 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

TEM (BP3 mode) Templates mode, which exhaustively derives a sub-grammar to generate a catalog of structural skeletons (TEMPLATES: section). → See B3

TEMP (mode) BP3’s structural exploration mode — exhaustively enumerates all structural skeletons that the grammar can produce (ignoring weights). The resulting catalog can optionally be used by ANAL as an alternative recognition strategy. TEMP is not a prerequisite for ANAL. In Shannon’s terms: builds the decoder’s dictionary. → See B8

Temperament Mathematical interval grid — division of frequency space into steps → See S9

Template Structural skeleton pre-calculated by the TEMP direction. Stored in the TEMPLATES: block. → See B10

Template matching The central mechanism of ANAL mode: superimposing a sequence to be analyzed onto the patterns defined by the grammar rules. → See B8

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

terminalActorMap Dictionary {BP3 terminal → actor} — allows the dispatcher to identify the actor → See S10, S13

Tetrachord/Jins 4-note fragment spanning a fourth — basic building block of Arabic and Turkish scales → See S9

Theka 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

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

Tihai In Indian music, a final 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āī Indian cadence where a motif is repeated exactly three times to land on sam. Corresponds to BP3’s SUB mode. → See B3, B4, B6

Time pattern In BP3, a symbol (t1, t2…) defining a relative duration in smooth time. In striated mode, time patterns have zero duration. → See B12

Time-object The elementary building block of BP3 — any sequence of messages possessing a duration. The generic term includes notes, Csound instructions, and any temporal event. → See B9

Time-setting Temporal placement of sound-objects under constraints (Bel 1992) → See B13, B9

Timewise File organization by measure then by instrument. → See I5

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

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

Tokenizer Step 1 — breaks the source into tokens, reads alphabets and octaves → See S10

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

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

Tonic shift transposition by changing the reference note — preserves all ratios → See S15

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

Topological properties Characteristics of a sound-object related to its neighborhood relationships (truncation, overlap, adjacency). → See B9

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 of the same level of abstraction → See M3

Transpiler a program that converts source code from one language to another at the same level of abstraction → See M7, S1

Transport Output protocol for timestamped data (Web Audio, MIDI, OSC) → See S10, S3

Tree (computer science) 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

Trigger An instantaneous pulse of zero duration → See S3

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

Tuning Concrete scale = which steps of the temperament to use + reference frequency → See S9

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

U

Undetermined rest Silence ... whose duration is calculated by PolyMake() → See B13

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 The |x| construction where the first occurrence sets a value and subsequent ones replicate it. Allows for the expression of exact repetition constraints impossible in CFGs. → See B6, S8

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. Tintāl has 4 vibhāgs of 4 beats each. → See B2, B3

Voice Melodic line within a part (for polyphony on a staff). → See 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: the postcondition has been weakened. → See L8

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

Weakly context-sensitive a class of languages more expressive than context-free grammars, but still parsable in polynomial time (TAG, CCG); BP3’s flags touch upon it, its variables exceed it; see L9 → See S1

WebAssembly (WASM) a binary execution format that allows compiled code (here BP3, written in C) to run in a browser → See S1

Weight Numerical value <N> or <N-M> controlling the probability of rule selection in RND mode. → See B10

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

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