The Setting
The graph data for two typed data channels consist of product profiles and paths with prescribed parity. The question is whether a forbidden configuration supplies all the required endpoints at once.
A pure type system specification consists of a set of sorts, an arbitrary axiom relation , and an arbitrary product-rule relation .β¦ Terms are variables, sort constants, applications , annotated abstractions , and dependent products .β¦ Displayed variable names stand for de Bruijn indices, with zero denoting the nearest binder; contexts are written newest first.
The typing judgement uses the specificationβs axiom and product rules together with variable introduction, weakening, abstraction, application, and conversion to a -convertible expected type having a sort. A valid context for is a finite context generated from the empty context by adjoining whenever for some sort .β¦
Full one-step reduction contracts to the capture-avoiding substitution and is closed under every term constructor, including annotations and binder bodies.β¦ The relation of convertibility is the least equivalence relation containing full one-step reduction.β¦ A normal form is a term that admits no full one-step reduction.β¦ A weakly normalizing term is a term from which finitely many full one-step reductions reach a normal form.β¦ Write for the unique full normal form of when it exists, with a fixed fallback otherwise.β¦
The normal form sort profile is the set of all sorts typing , as in (1). (1)β¦ A feasible sort profile is a nonempty set equal to for some valid context and some normal term .β¦
The axiom profile and the product output profile are the sets specified in (2). (2) A feasible product profile triple consists of feasible sort profiles with ; its domain profile is and its codomain profile is .β¦
Signed Profile Graphs
The primary and secondary graphs are signed directed graphs on sets of sorts. An edge has sign when positive and sign when negative. A signed directed walk in graph is a finite walk whose number of negative edges has parity ; repeated edges are permitted, and an empty walk has parity .β¦ The positive reachability relation in graph , written , relates vertices and when there is a finite, possibly empty walk from to consisting entirely of positive edges.β¦ Directed reachability in a signed graph is the relation between pairs of vertices joined by a finite walk of either parity.β¦
The primary graph, indexed by , has positive inclusion edges when are feasible and . Each feasible product profile triple gives a negative domain edge and a positive codomain edge . These are exactly its edges.
Fix a family of sets of sorts. The observation layers for are the profiles in the family of (3). (3)β¦ The secondary graph, indexed by , consists of positive primary edges whose endpoints belong to , and negative edges arising from feasible product profile triples with .β¦
A direct observation layer is a member of for which some form a feasible product profile triple .β¦ A plain observation layer is a profile with both an even signed walk and an odd signed walk in the secondary graph to direct observation layers, which may differ.β¦
A strongly connected component of a signed graph is the set of vertices mutually reachable with some vertex .β¦ A forbidden configuration for is a strongly connected component of the secondary graph whose vertices are all plain observation layers, which contains a negative edge, and for which there are a feasible product profile triple and a sort with , a nonempty axiom profile , and positive primary reachability .
The Claim
Theorem 1. Suppose admits a forbidden configuration. There are a strongly connected component of the secondary graph, a sort , feasible product profile triples and , and direct observation layers satisfying (4). (4)β¦
What Is Checked
The statement is over arbitrary pure type system specifications and families of sort sets admitting a forbidden configuration in their secondary signed graph.