Glossary of Formal Languages and 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

$\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

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

\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

_tempo()
BP3’s special function (T43 in the C code) that modifies the local tempo. Changes the speed/scaling ratio in the polymetric expansion algorithm.
→ 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

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

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

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

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

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)
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: $\langle n \rangle \Downarrow n$ is an axiom because a number always evaluates to itself.
→ See L6, L8

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

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

B

bp3_set_object_duration
WASM API to communicate a concrete duration (ms) to a custom terminal
→ See S10

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

Bidirectionality
Property of a grammatical formalism that can be used for both generation (producing strings) and recognition (parsing 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

Birman-Ullman (paradox of)
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, 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 ( $\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

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

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

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

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

CFG (Context-Free Grammar)
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 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

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
JS program that transforms .bp source into BP3 grammar + control table
→ See S10

Compiler correctness
property stating that compilation preserves meaning. Formally: Morris’s 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). 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

Constrained generation
Generation that must produce a specific string $$w$$ , not just any string from the language. Can be NP-hard from Type 2.
→ See L17

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. 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 where all rules are of the form $A \to \gamma$ (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
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

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

CYK (Cocke-Younger-Kasami): A bottom-up parsing algorithm using dynamic programming. Works 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, intrinsically bidirectional thanks to unification, but with asymmetric pathologies (different infinite recursions in each direction).

Declarativity

Property of a grammar that separates what it says (the linguistic content) from how it is processed (the direction, the 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

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) up to a string containing only terminals.
→ See B1, B2, B3, L6

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

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

Determined Rest
Rest of fixed duration, denoted - 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 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 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

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

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

embedInStream
SuperCollider method that inserts a pattern’s events into a routine’s (Prout) stream, allowing dynamic control of the flow.
→ 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
Third step — translates the AST into BP3 grammar with a flat alphabet
→ 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

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

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 simple names (no OCT encoding) — 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

Free generation
Generation without an output objective — rules are applied, and the result is observed. Always $\mathcal{O}(n)$ , regardless of grammar class.
→ See L17

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

FST (Finite-State Transducer): 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): Ranta’s multilingual grammatical formalism (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 integrated into procedural grammars.
→ See L16

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

General MIDI (GM)
standard defining 128 sounds numbered identically across 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. 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

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 class ( $$k$$ ): The level in the Chomsky hierarchy. $$k = 3$$ (regular), $$k = 2$$ (context-free), $$k = 2^+$$ (mildly context-sensitive), $$k = 1$$ (context-sensitive), $$k = 0$$ (recursively enumerable).

Differential coupling

The fact that generation and recognition are both sensitive to both axes (grammar class and task specification), but with an inverted primary sensitivity. Generation reacts primarily to the task; recognition reacts primarily to the grammar.
→ See L17

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

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

H

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

Heatmap
Visual representation of a matrix where color codes the intensity of a value. Here, green codes low complexity ( $\mathcal{O}(n)$ ) and dark gray codes undecidability.
→ See L17

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

IDyOM (Information Dynamics of Music): 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 the rule to the 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

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

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

Inherent ambiguity
A property of a language (not a grammar) such that any grammar generating it is ambiguous. Discovered by Parikh (1966).
→ See L15

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

Injective (function)
A function that maps distinct inputs to distinct outputs. Generation is injective in $$d$$ (one path → one sentence); parsing is non-injective (one sentence → multiple trees).
→ See L15

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

Invariant
A property of the generated code that must always be true (e.g., no comments in an SC array).
→ See B7, 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

J

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

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

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 impractical.”
→ See L16

Kathak
Classical dance of North India, linked to tabla. Tablist-dancer interactions are a foundational 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, B7, B8

Khali
“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 any continuous function on a domain has a least fixed point, obtained as the limit of successive approximations.
→ See L7

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)
A rule that rewrites a non-terminal to 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

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

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

Legato
Connected playing style, where notes flow into 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)
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 in the work string is rewritten 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, M7

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

Lookahead

The 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

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

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

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

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

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

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

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): Subfield of NLP concerned with text generation. Reiter & Dale’s pipeline breaks down 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-Markovian process (with memory)
Stochastic process where the probability of an event depends on the history of past events.
→ See B1

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

Normalization
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

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

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

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

P

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

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

Parsing (syntactic analysis)
The process which, 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 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

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

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

PCFG (Probabilistic CFG)
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

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

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

Phase diagram
BP3’s internal data structure (Maxconc × Maxevent grid) that represents the temporal placement of all events after polymetric expansion.
→ See B12

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

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

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

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

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

Prolonged Rest (UndeterminedRest)
Rest of indefinite duration, denoted ... in BP3. Equivalent to a fermata.
→ 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. Describe how we perceive tension/resolution relationships.
→ See M6

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

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

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, allowing it to manage nesting.
→ See L1, M2

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

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

R

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

Recursion
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
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
Persistent code session (sclang, Python) — bidirectional: executes code AND returns values
→ See S10

Resolver
Dispatcher component that translates names → frequencies (tuning) and names → routes (routing)
→ See S10

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)
Right side of a rule — the result of rewriting. Can be empty (ε-production). 23 possible element types.
→ See B10, B3

Rightmost 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
AST node representing a BP3 production rule with grammar number, rule number, weight, flags, LHS, and RHS.
→ See B7

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

S

_script(CTn)
Table-based control mechanism — BPscript qualifiers are compiled into indices in a control table
→ See S10

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, 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 notion of the arbitrariness of the sign.
→ See M4

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

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

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
BP3’s temporal mode (_smooth) where durations are intrinsic properties of objects, without reference to a pulse. Implements Boulez’s “smooth time”.
→ See B12

Smooth time (temps lisse)
Boulez’s concept (1963) referring to a temporal flow without regular metric markers. A textile metaphor (without striations), not a mathematical property (continuity).
→ See B12

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

Sound-object
A time-object enriched with metric and topological properties, ready to be placed in time by the time-setting algorithm.
→ See B9

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

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

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

Striated time (temps strié)
Boulez’s concept (1963) referring to a temporal flow divided by regular markers (pulse, measure). BP3’s default mode (_striated).
→ See B12

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

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

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

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

Syntax tree
Tree 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

Task specification
What the operation is asked to produce. For generation: free, terminating, constrained. For recognition: membership, one tree, all trees.
→ See L17

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

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

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

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

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

Theka
Basic pattern of an Indian tāla, played as an ostinato by the tabla. 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 as note& (start) and &note (end) in BP3.
→ See B5, B7

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, B5, 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
A constraint satisfaction algorithm that calculates the physical placement of sound-objects in time, taking into account their properties and context.
→ See B9

Timed token
Timestamped event produced by BP3: {terminal, start, end}
→ See S10

Timewise
File organization 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

Tokenizer
First step — breaks source into tokens
→ 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

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 source-to-source translator between two languages of the same level of abstraction (here, BP3 to SuperCollider).
→ See B7, M7

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

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

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 whose duration is calculated by context, denoted _ 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
A |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: 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

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

Wildcard (joker)
A ?N construction that captures an arbitrary portion of the string. In PROD mode: captures on the left side, reinserts 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

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