{"template":"sigconf","title":"Stratified Semantics for Negative Layout Constraints","short_title":"Stratified Semantics for Negative Layout Constraints","authors":[{"name":"Mireille D. Saunac","affiliations":[1],"email":"m.saunac@aurevin.example","corresponding":true},{"name":"Kenjiro Matsunobe","affiliations":[2]},{"name":"Eloísa Antúnez Cárden","affiliations":[3]}],"affiliations":["Department of Foundations of Computing, Institut Aurevin, Toulouse, France","Center for Language Engineering, Suirei Institute of Technology, Okayama, Japan","Laboratory for Document Systems, Instituto Meridión, Rosario, Argentina"],"abstract":"Page construction languages let authors reserve space and test geometric properties of earlier layout results. In a bound document the reservation can itself be observable, and the code that reports the result of a layout test can invalidate the test. We give a typed intermediate language for intentional blanks in which content, declarations of intent, and visible evidence of intent have separate effects. The semantics computes ordinary occupancy by stratified fixed points over a frozen page map, then emits attestations that carry no ordinary occupancy at their authorized sites. We prove convergence and preservation of occupancy under emission and characterize the cycles rejected by a syntax-directed checker. A separate validator detects changes to the compiled page stream after imposition. On 240 document fixtures, 228 are in the accepted fragment, and their outputs match independently specified page contracts. The 12 rejected fixtures produce 8 negative-cycle diagnostics and 4 scope diagnostics. The language distinguishes a page that prints a blankness notice from a blank page on which no notice was intended, even when both have identical ordinary content.","keywords":["document languages","stratified negation","effect systems","pagination","translation validation"],"body":"# Introduction {#sec:intro}\n\nA print contract can require page 48 to exist, have no running head or folio, and carry the sentence “This page intentionally left blank.” Existence is an obligation of pagination. The choice to omit the folio is an obligation of the page style. The sentence is typically inserted by a person after reviewing a proof. Moving that last operation into a program exposes a difficulty. If the operation is guarded by a test that the page has no marks, its result invalidates its premise. If the operation is unconditional, an editorial change may place a table on page 48 beside an authoritative statement about the table's absence.\n\nSome print workflows keep the sentence in a separate layer of the page file, which helps the press operator inspect the output [@havelin2015signature; @osada2020layer]. Layer membership alone supplies a weak specification. A line in the attestation layer can still refer to the wrong page, and a mark in the body layer can still be absent because a resource failed to load. Several systems in our fixture set pass a Boolean called empty between layout stages. The Boolean has meant, at different points in the same pipeline, that the page has no source paragraphs, that it has supplied no boxes to the compositor, or that the display list can be erased without removing any body ink. Only the last of those interpretations is even defined on the artifacts received by the printer.\n\nOn a spread whose left leaf reports a blank on the right, the proposition and its rendering have different addresses. Imposition moves physical surfaces while preserving the logical address named in the notice.\n\nWe take the page map as fixed and give ordinary occupancy one bit per page. @sec:language defines the constraints, @sec:compile describes the linker and validator, and @sec:evaluation compares their output with a set of print contracts.\n\n# Background {#sec:related}\n\nKnuth and Plass use boxes, glue, and penalties to choose paragraph breaks globally [@knuthplass1981]. The page builder in TeX [@knuth1984] handles a subsequent optimization problem and exposes page-dependent behavior through its output routine. Document algebras such as the libraries of Hughes and Wadler specify line structure compositionally [@hughes1995; @wadler2003]. Their empty document serves as an identity for concatenation. An empty mark list contributes zero ordinary occupancy at a page position. It has extent and is observable even when its display list has length zero. In particular, concatenating a blank leaf with an eight-page gathering changes the number of pages in the document.\n\nWe apply finite monotone dataflow [@kildall1973; @cousot1977] to a stratified relation over page positions [@apt1988; @abiteboul1995]. An SCC decomposition [@tarjan1972] yields the components. The report of a successful check needs a separate effect. Treating it as another occupancy fact can invalidate the result.\n\nOur checker follows the standard use of judgments to restrict what programs can express [@milner1978; @pierce2002]. The witness layer requires a smaller output vocabulary than the ordinary layer. Work on final-artifact validation [@pnueli1998; @necula1997] suggests a practical split between finding an appropriate compilation result and checking a result already found. Print-specific precursors infer likely insertions from imposed page streams [@delario2019imposition] or carry manifest labels across page extraction [@balar2023manifest]. We keep a logical page identifier on every print surface and transport certificate targets using that identifier.\n\n# A Core Language for Page Intent {#sec:language}\n\n## Pages and marks\n\nA preprocessing pass fixes a map $P$ of logical page identifiers, their trim rectangles, and a region reserved for evidence on each eligible site. This pass can run a general page builder. Once the map is fixed, every block in the core language has a site and a bounded rectangle. Ordinary blocks draw from a finite set of resource-resolved marks. Normalization removes zero-area clips, fully transparent marks, and whitespace-only text. The remaining primitive operations are clipped within the trim rectangle. We classify occupancy by the presence of an ordinary operation in that normalized list, even if another ordinary block later paints it over. This choice gives a reproducible pre-raster contract. A program that paints white over a black label has emitted two operations. A program whose label reduces to zero area has emitted neither.\n\nA declaration $I(p)$ records the author's reservation of $p$ for absence of ordinary marks. A leaf can end up empty without such a declaration, for instance when its float fits on the preceding page. A declared leaf with positive occupancy fails compilation.\n\nAn attestation is a value with two page arguments, a site $p$ and a subject $q$. Its proposition is $I(q)\\land\\neg o_q$, where $o_q$ is ordinary occupancy. Its rendering is licensed by a capability for the pair $(p,q)$ and a certified region at $p$. When $p=q$ the permitted phrasing includes the usual notice for an intentional blank. When $p\\ne q$ the referenced page must appear in the output, either as a logical reference in a machine-readable edition or as a resolved page identifier in the printed string. A notice on p. 48 about the absence of content on p. 47 therefore carries two distinguishable identifiers even if the two pages have the same measured ink density.\n\nThe approved region can hold one compact witness per site in the core language. The glyph stream comes from a fixed dictionary keyed by locale and proposition form. The untrusted author does not supply the string as an argument. This restriction prevents a paragraph from becoming free of occupancy by enclosing it in a witness declaration. A proof for page 48 can occupy 42 mm of its width. The value being proved still has no ordinary occupancy.\n\nThe effect checker uses two primitive emissions, ordinary marks at $p$ and witness marks at $p$ about $q$. In @eq:witness, $A$ is the set of authorized pairs and $D$ the set of declared subjects. A witness command has no guard-typed result. The only page-indexed inputs to guards are ordinary occupancy reads. The judgment assigns authority to attempt emission. Actual emission still depends on the valuation and on the witness glyphs fitting in the reserved region.\n\n$$\n\\frac{(p,q)\\in A\\qquad q\\in D}{A;D\\vdash\\operatorname{witness}(p,q):\\operatorname{Evidence}(p,q)}\n\\label{eq:witness}\n$$\n\n## Ordinary occupancy\n\nAn ordinary block $b$ has a site $s(b)$, a normalized list of operations, and a guard $g_b$. The syntax of a guard is a constant, an occupancy literal, or an expression obtained by conjunction and disjunction. Negative reads appear as literals $\\neg o_q$. Guards may refer to the same site as their block. Define $a_b=1$ exactly when normalization retains at least one operation. The program supplies one equation per page as in @eq:occupancy.\n\n$$\no_p = \\bigvee_{b:s(b)=p}\\left(a_b\\land g_b(o)\\right).\n\\label{eq:occupancy}\n$$\n\nAn empty disjunction is false. We draw an edge from each read position to its output position and label it with the sign of the literal. An SCC is admissible when every internal edge is positive. The compiler solves admissible components in topological order, substituting already fixed values for external literals. It computes the least solution in the Boolean lattice of the component, beginning with all bits clear. There can be other fixed points even when all reads are positive. In a two-page spread where each page gets a folio only if the facing page is occupied, both folios are absent in the least solution. Adding a body block to either one places both folios.\n\nNegative reads complicate the choice of a solution. Suppose each of two empty leaves prints an ordinary line if its neighbor is empty. There are two fixed points, each certifying the other leaf at the expense of its own blankness. The two results are exchanged by the automorphism that swaps the logical leaves and their rules. A fixed point chosen by increasing page number violates that symmetry. If a single leaf prints an ordinary line when it is itself empty, the equation becomes $o_p=\\neg o_p$ and there is no two-valued fixed point at all. Our checker rejects both cases. Some SCCs with syntactically negative internal edges do have a unique solution, for example if an unconditional mark forces a bit high. The present checker intentionally uses guards' static read sets, and rejects these SCCs without trying to simplify them using possible solutions.\n\n## Emission and observation\n\nOrdinary emission traverses blocks in source order after valuation. Within each logical page, it concatenates the normalized marks of enabled blocks. Thus a guard's evaluation order can affect compilation cost but cannot change paint order. A witness pass takes the resulting valuation and emits a draw operation only for a declared and unoccupied subject, after checking the capability and site rectangle. Reserved witness sites are optional on any page, including pages with ordinary material. The common self-attestation uses a site on the subject. A certificate printed on a binding slip can name another page without changing the occupancy of either page.\n\nLet $\\pi_O$ project a decorated display list to its ordinary operations. Let $R(o)$ render the ordinary blocks under valuation $o$, and let $W(o,I)$ insert the licensed witnesses into a separate plane. The invariant is @eq:projection. It is equality of per-page ordered lists after normalization.\n\n$$\n\\pi_O\\bigl(R(o)\\oplus W(o,I)\\bigr)=R(o).\n\\label{eq:projection}\n$$\n\nA preview can return the unprojected stream to a press operator and the ordinary projection to the editor. A scanner given loose pages cannot distinguish a certified blank from the same sentence set as an ordinary paragraph.\n\n# Implementation and Independent Validation {#sec:compile}\n\nThe linker assigns a fresh logical key to every generated leaf. A private constructor represents witness capability in the intermediate language. The front end exposes it through a check on the declared site and subject. The linker checks edition-specific glyph bounds once the font is known.\n\n## Solving the page graph\n\n@alg:solve builds the signed dependency graph, rejects each inadmissible component with a cycle witness, and fills the valuation before rendering. Internally we compile each guard into a tree of conjunction and disjunction nodes. After external literals have been substituted, initially true leaves go onto a queue. Each parent maintains a count of unsatisfied children for conjunction or a single latch for disjunction. A true clause wakes its site once and may wake new internal occurrences of the site bit. This representation avoids rescanning all guards after each addition. Each node undergoes at most one promotion inside its component.\n\n```algorithm {#alg:solve caption=\"Evaluation on a frozen page map\"}\nRequire: linked pages $P$, ordinary blocks $B$, intent $I$\n$G \\gets \\operatorname{SignedReads}(P,B)$\nfor $C$ in source-first component order of $G$ do\n    if $C$ contains an internal negative edge then\n        return a cycle diagnostic\n    end if\n    $o_C \\gets \\operatorname{Propagate}(C,o)$\nend for\nif some declared page is occupied then\n    return an intent diagnostic\nend if\nreturn $\\operatorname{Emit}(P,B,o,I)$\n```\n\nThe graph stage and propagation together cost $O(n+m)$ time and space, where $n$ counts page positions and $m$ counts all guard syntax nodes, including repeated occurrences. That bound excludes glyph shaping, geometry normalization, and emitting the marks. Counting just edges between distinct pages can undercount the work by an arbitrary factor. A hundred uses of a single page key can trigger one graph edge and a hundred separate guard updates. We retain occurrence lists in addition to deduplicated graph edges. The checker reports a negative read with the source span of its literal, then gives a positive or negative return path from the output site to its input site within the SCC.\n\nAn attempted ordinary read of a witness fails in the front end. Negative recursion over ordinary occupancy fails at linking. @sec:proof gives the projection argument.\n\n## Checking the printed result\n\nThe compiler emits side data comprising page identifiers, per-page normalized ordinary mark lists, and positions and subjects of witnesses. The validator independently interprets guards after reconstructing and solving the signed graph from the checked source. It compares the target stream, after normalization and inverse imposition, with the expected ordinary lists and a dictionary expansion of the witness declarations. It also checks that physical rectangles match those supplied by the imposition map. We compare canonical display commands, including the font resource identifier and the glyph transform. The validator cannot infer a reliable claim from the typographic content of a scanned surface.\n\nThe validator detects three edits drawn from production reports [@osada2020layer; @balar2023manifest]. It catches dropped leaves by key, witnesses changed to ordinary text by effect, and swapped subjects by reference identity.\n\n# Evaluation {#sec:evaluation}\n\n## Corpus and outcomes\n\nWe prepared 240 fixtures in 12 families of 20. Families vary signature size, chapter boundaries, and whether evidence is reserved on the subject or elsewhere. @tbl:fixtures groups cases by page topology. The sample includes 12 fixtures constructed to trigger diagnostics.\n\nTwo readers independently transcribed the expected page keys, ordinary marks, and witness pairs before running any compiler. They reconciled 6 mirrored coordinates and 2 supplement identifiers by recording physical coordinates and logical identifiers in separate fields. Invalid cases specify a single expected error class and offending clause.\n\nTable: Fixture coverage and strict agreement with the reference on accepted cases. Denominators for the three output strategies exclude fixtures with expected diagnostics. {#tbl:fixtures span=full}\n\n| Logical topology | Fixtures | Valid | Inline | Late pass | Stratified |\n|:-----------------|---------:|------:|-------:|----------:|-----------:|\n| Single-sided | 90 | 90 | 72 | 87 | 90 |\n| Facing spreads | 98 | 92 | 46 | 72 | 92 |\n| Multiple signatures | 52 | 46 | 20 | 27 | 46 |\n| Total | 240 | 228 | 138 | 186 | 228 |\n\nThe inline baseline treats announcements as ordinary display objects and tests whether the list at its current position is empty in emitter order. It was allowed to read the intent bit and use the same dictionary as the other strategies. The late-pass baseline solves ordinary occupancy using the same stratified solver, suppresses announcements during ordinary rendering, and adds notices based on intent and emptiness. It locates the target leaf by the current emitted position and always inserts the notice on that target. Both baselines use the same resource normalization. We score strict agreement on page identities and provenance, so a line produced at the right place without a recoverable subject identity passes only if the implied identity from its site is the required one.\n\n@fig:differences decomposes the differences. A misplaced notice may also have a false subject once later content arrives. We count just one failure per fixture using the priority order: missing or extra leaf, wrong site or subject, then wrong occupancy or intent. The main deficit of the late pass arises in fixtures that place evidence on a page other than the subject. The three single-sided cases in which that approach fails use a reserved machine-readable receipt on the preceding leaf.\n\n```chart {#fig:differences span=full caption=\"First difference from the reference on the 228 valid fixtures. Placement includes the evidence subject and site. Both baselines receive the same trim and resource data.\"}\n{\"type\":\"heatmap\",\"rows\":[\"Inline\",\"Late pass\",\"Stratified\"],\"cols\":[\"Page count or identity\",\"Placement\",\"Occupancy or intent\"],\"values\":[[12,43,35],[0,42,0],[0,0,0]],\"colormap\":\"Blues\",\"annotate\":true,\"fmt\":\".0f\",\"colorbar\":\"Fixtures\",\"size\":[6.5,2.4]}\n```\n\nThe signed checker reports eight negative cycles, four in facing spreads and four in longer impositions. The four scope errors consist of two sites with a forbidden subject and two attempts to move a certificate to a leaf lacking a reserved region. The absence of a reserved region fails before glyph metrics are considered. We also fed the validator 24 edited streams, within a separate test suite of 12 documents with two edits per document. @tbl:mutations reports detections by edit. The stream comparison strips trace-only mark IDs but retains semantic layer and witness identifiers.\n\nTable: Validation of single edits to compiled streams. Each edited stream has one injected difference. The first three rows are semantic differences and the final row is a provenance-preserving reserialization. {#tbl:mutations}\n\n| Edit | Streams | Rejected |\n|:-----|--------:|---------:|\n| Omitted blank leaf | 6 | 6 |\n| Ordinary copy of witness | 6 | 6 |\n| Transposed subjects | 6 | 6 |\n| Object serialization order | 6 | 0 |\n\n## Cost measurements\n\nThe scaling suite is independent of the contract fixtures. We build lists of size 128 through 32,768 logical pages. A chain distribution gives all but the first page exactly one positive predecessor. A spread distribution gives the two leaves of a spread mutual positive reads and gives the second leaf a single dependency on the preceding spread. A dense distribution groups 32 pages into components with up to eight incoming positive reads per page and connects each block to its predecessor using a lower-stratum negative guard. Every group has a fixed, seed-dependent opportunity for ordinary marks. A generator chooses that seed from a fixed set of 30 seeds per size and graph family. The parser consumes the same in-memory representation in every condition. We timed normalization of guard expressions, graph construction and valuation, excluding geometry and IO. The test harness runs each seed twice before recording one elapsed time; generator and GC initialization are outside the timed section. The fixed workstation ran on a single pinned core. The elapsed-time distribution includes individual GC pauses within the timed section.\n\n@fig:scaling gives medians across the 30 generated instances in each condition, with bounds of the interquartile range given in @tbl:timing for the largest size. These intervals describe run and instance dispersion under the specified generator. We use the same seed index across the graph families but do not treat graph families as control treatments for computing a speed ratio.\n\n![End-to-end analysis time by logical page count. Each point is the median of 30 generated instances. Both axes are logarithmic.](graph-scaling){#fig:scaling span=full}\n\nTable: Core analysis time for 32,768 logical pages. Quartiles describe 30 runs per graph family. {#tbl:timing}\n\n| Graph family | Q1 (ms) | Median (ms) | Q3 (ms) |\n|:-------------|--------:|------------:|--------:|\n| Chain | 27.0 | 28.4 | 31.2 |\n| Spread | 37.8 | 40.6 | 43.1 |\n| Dense blocks | 113.1 | 119.7 | 131.5 |\n\nAn edit invalidates reachable SCCs and the witness sites reading them. For @fig:edit we grouped a 1,024-page document into signatures of 16 pages and chained dependencies within groups of varying length. We edited one ordinary clause at the first or final signature, then reset. Counts are invariant across groups of equal size. Rebuilding clears affected occupancy first, so removing the sole seed of a positive cycle can delete all its folios.\n\n```chart {#fig:edit span=full caption=\"Extent of incremental invalidation in the 1,024-page suite. Sites are counted once even when their ordinary marks and their witnesses are both invalidated.\"}\n{\"type\":\"line\",\"xlabel\":\"Signatures per dependency group\",\"ylabel\":\"Invalidated logical pages\",\"x\":[1,2,4,8,16,32,64],\"xscale\":\"log\",\"yscale\":\"log\",\"series\":[{\"label\":\"First signature\",\"y\":[16,32,64,128,256,512,1024],\"marker\":\"o\"},{\"label\":\"Final signature\",\"y\":[16,16,16,16,16,16,16],\"marker\":\"s\",\"style\":\"dashed\"}],\"size\":[6.4,2.5],\"legend\":\"upper left\"}\n```\n\nThe count includes every invalidation. A later compiler pass could stop propagation as soon as it reestablishes the previous valuation.\n\n# Discussion {#sec:discussion}\n\nA practical issue is whether intentionality should be inferred. When the page builder opens every chapter on a recto, the resulting verso is often treated as a reserved blank. Some contracts instead allow ordinary material there, such as a plate or a correction inserted late. A builder may choose to synthesize a declaration from the chapter rule, provided the author consents to checking it at the end. Inferring $I$ by testing that the final mark list is empty would let ordinary content disappear unnoticed when the typesetter loses a link to a resource. Express declaration before testing occupancy preserves the evidence needed to diagnose the missing content as separately unexpected.\n\nThe fixed page map is a restriction on optimization. A witness cannot borrow additional vertical space, push a paragraph onto a later page, or ask for a new empty leaf as part of its rendering. Suppose a printer needs an additional evidence page listing the blankness obligations of a signature. The page must be allocated during initial layout. Once registered as an evidence site it may testify for an adjacent eligible leaf under the core rules. A multi-subject receipt would require a checked list of target identities and a statically bounded witness region. Testing whether the receipt itself is an intentional blank still makes sense if all its emitted marks have the restricted witness effect. Therefore a single physical sheet could carry an exact account of several intentional absences while contributing zero ordinary occupancy.\n\nInk printed on the verso can show through a certified recto. Legibility and optical detection depend on paper and illumination. A verifier for visible pigment could classify an opaque white rectangle differently from our ordinary mark count. It would also have to account for occlusion, which can invalidate monotonicity under ordinary mark addition.\n\n\\appendix\n\n# Proof Details {#sec:proof}\n\n::: proposition {#prop:strata title=\"Termination and uniqueness of the stratified least solution\"}\nFor a finite linked program with no internal negative edge in any strongly connected component, component evaluation terminates. The stratified least solution is independent of the order in which incomparable components are evaluated and the order in which available facts are propagated inside a component.\n:::\n\n::: proof\nAfter substitution of external reads, all variable occurrences in the equations of a component are positive. The right-hand side of @eq:occupancy hence gives a monotone map on a finite Boolean lattice. From bottom, iteration is an ascending chain and yields the least fixed point by finite stabilization [@tarski1955]. The component implementation promotes bits one at a time when the right-hand side permits promotion. Every promoted bit belongs to every fixed point extending the already substituted predecessors, by induction on promotions. At quiescence each true clause has been propagated and each promoted bit remains justified by monotonicity. The result is a fixed point and is below every other fixed point. Incomparable components do not read one another. Their evaluation order cannot change the substituted values seen by either.\n:::\n\nWitness effects preserve ordinary absence. The ordinary emitter computes the precise marks whose feasibility was used to assign $a_b$. Witness expansion adds only commands bearing the witness effect, all with valid subjects and approved sites. Projection removes just those commands. Thus @eq:projection follows by source-order induction over emitted blocks and a final pass over witness insertion positions. It continues to hold under injective renaming of page identifiers when capabilities and declared subjects are transported by the same renaming. Imposition supplies an injective mapping to print surfaces. Page numbers alone can fail that property when signatures restart numbering.\n\nWe tested the propagation proof obligations separately using generated small guards in the style of QuickCheck [@claessen2000]. For every admissible program with at most eight pages in that suite, we compared the least fixed point of each stratum with exhaustive enumeration within the stratum. For every rejected graph, replay traversed the implicated literal and the reported return path. When a comparison failed during development, the shrinker removed blocks and then simplified guards while preserving the predicate that failed, following the usual approach to input minimization [@zeller2002]. The largest class of early mismatches arose because flattening folded the reserved display layer into ordinary ink. Keeping the original provenance through normalization removed that discrepancy.\n\n# An Edition with a Duplicated Folio {#sec:example}\n\nConsider two gatherings compiled separately, each with a locally numbered page 16. In the first gathering that page closes a chapter. In the second gathering the corresponding page is reserved. Suppose evidence of the latter reservation belongs on the inward-facing page 15 in the second gathering. The unsuffixed string “16” names two logical sites. The linker requires an edition-specific site key in the receipt constructor, then emits the human-readable folio according to the witness dictionary. Our press profiles call that leaf “16 of gathering II” even if it physically faces page 1 of another gathering on the imposed sheet. After the sheet is folded the key still refers to the second logical page 16. Reusing the first key would survive a test comparing the visible number alone. The validator checks the resolved logical identity and would reject the stream.\n\nThe same example provides a regression for blank-page preservation under output extraction. Extracting gathering II must retain its reserved leaf and the proof site. Extracting only page 15 can retain the witness if the extraction contract permits a reference to an external subject. The core compiler treats that reference as unlinked. An edition authority can supply the missing contract as an import, but the current validator requires the subject's attachment in the same stream. A print consisting of that single notice is evidence of a page that the print does not itself contain.\n","bibliography":"@article{knuthplass1981,\n  author = {Knuth, Donald E. and Plass, Michael F.},\n  title = {Breaking Paragraphs into Lines},\n  journal = {Software: Practice and Experience},\n  year = {1981},\n  volume = {11},\n  pages = {1119--1184}\n}\n@book{knuth1984,\n  author = {Knuth, Donald E.},\n  title = {The {TeX}book},\n  publisher = {Addison-Wesley},\n  year = {1984}\n}\n@incollection{hughes1995,\n  author = {Hughes, John},\n  title = {The Design of a Pretty-Printing Library},\n  booktitle = {Advanced Functional Programming},\n  publisher = {Springer},\n  year = {1995}\n}\n@incollection{wadler2003,\n  author = {Wadler, Philip},\n  title = {A Prettier Printer},\n  booktitle = {The Fun of Programming},\n  publisher = {Palgrave Macmillan},\n  year = {2003}\n}\n@inproceedings{kildall1973,\n  author = {Kildall, Gary A.},\n  title = {A Unified Approach to Global Program Optimization},\n  booktitle = {Proceedings of the ACM Symposium on Principles of Programming Languages},\n  year = {1973}\n}\n@inproceedings{cousot1977,\n  author = {Cousot, Patrick and Cousot, Radhia},\n  title = {Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints},\n  booktitle = {Proceedings of the ACM Symposium on Principles of Programming Languages},\n  year = {1977}\n}\n@incollection{apt1988,\n  author = {Apt, Krzysztof R. and Blair, Howard A. and Walker, Adrian},\n  title = {Towards a Theory of Declarative Knowledge},\n  booktitle = {Foundations of Deductive Databases and Logic Programming},\n  publisher = {Morgan Kaufmann},\n  year = {1988}\n}\n@book{abiteboul1995,\n  author = {Abiteboul, Serge and Hull, Richard and Vianu, Victor},\n  title = {Foundations of Databases},\n  publisher = {Addison-Wesley},\n  year = {1995}\n}\n@article{tarjan1972,\n  author = {Tarjan, Robert},\n  title = {Depth-First Search and Linear Graph Algorithms},\n  journal = {SIAM Journal on Computing},\n  year = {1972},\n  volume = {1},\n  pages = {146--160}\n}\n@article{milner1978,\n  author = {Milner, Robin},\n  title = {A Theory of Type Polymorphism in Programming},\n  journal = {Journal of Computer and System Sciences},\n  volume = {17},\n  pages = {348--375},\n  year = {1978}\n}\n@book{pierce2002,\n  author = {Pierce, Benjamin C.},\n  title = {Types and Programming Languages},\n  publisher = {MIT Press},\n  year = {2002}\n}\n@inproceedings{pnueli1998,\n  author = {Pnueli, Amir and Siegel, Michael and Singerman, Eli},\n  title = {Translation Validation},\n  booktitle = {Tools and Algorithms for the Construction and Analysis of Systems},\n  publisher = {Springer},\n  year = {1998}\n}\n@inproceedings{necula1997,\n  author = {Necula, George C.},\n  title = {Proof-Carrying Code},\n  booktitle = {Proceedings of the ACM Symposium on Principles of Programming Languages},\n  year = {1997}\n}\n@article{tarski1955,\n  author = {Tarski, Alfred},\n  title = {A Lattice-Theoretical Fixpoint Theorem and Its Applications},\n  journal = {Pacific Journal of Mathematics},\n  volume = {5},\n  pages = {285--309},\n  year = {1955}\n}\n@inproceedings{claessen2000,\n  author = {Claessen, Koen and Hughes, John},\n  title = {{QuickCheck}: A Lightweight Tool for Random Testing of {Haskell} Programs},\n  booktitle = {Proceedings of the ACM SIGPLAN International Conference on Functional Programming},\n  year = {2000}\n}\n@article{zeller2002,\n  author = {Zeller, Andreas and Hildebrandt, Ralf},\n  title = {Simplifying and Isolating Failure-Inducing Input},\n  journal = {IEEE Transactions on Software Engineering},\n  volume = {28},\n  pages = {183--200},\n  year = {2002}\n}\n@article{havelin2015signature,\n  author = {Havelin, Dagmar and Forten, Louis J.},\n  title = {Signature Boundaries and the Attribution of Unprinted Surfaces},\n  journal = {Journal of Composition Systems},\n  volume = {19},\n  pages = {41--57},\n  year = {2015}\n}\n@inproceedings{osada2020layer,\n  author = {Osada, Mio and Balcarek, Tatiana},\n  title = {Layer Permissions for Supplementary Marks in Final Art},\n  booktitle = {Workshop on Print Workflow Semantics},\n  year = {2020}\n}\n@inproceedings{delario2019imposition,\n  author = {Delario, Inés M. and Amseld, Bertil},\n  title = {Recognizing Inserted Leaves in Imposed Print Streams},\n  booktitle = {Symposium on Archival Document Engineering},\n  year = {2019}\n}\n@article{balar2023manifest,\n  author = {Balar, Meltem and Steunissen, Frits},\n  title = {Transport of Leaf Manifests through Document Extraction},\n  journal = {Transactions on Publishing Systems},\n  volume = {8},\n  pages = {119--146},\n  year = {2023}\n}","figures":[{"id":"graph-scaling","kind":"chart","data":"{\"type\":\"line\",\"xlabel\":\"Logical pages\",\"ylabel\":\"Median analysis time (ms)\",\"x\":[128,512,2048,8192,32768],\"xscale\":\"log\",\"yscale\":\"log\",\"series\":[{\"label\":\"Chain\",\"y\":[0.19,0.52,1.78,7.2,28.4],\"marker\":\"o\"},{\"label\":\"Spread\",\"y\":[0.23,0.69,2.55,10.1,40.6],\"marker\":\"s\"},{\"label\":\"Dense blocks\",\"y\":[0.52,1.79,7.15,29.8,119.7],\"marker\":\"^\"}],\"legend\":\"upper left\",\"size\":[6.4,2.5]}"}],"acknowledgments":"We thank the composition staff at the Institut Aurevin for identifying imposition cases that our original grammar could not express.","options":{"venue_note":"Preprint.","ccs":["Software and its engineering → Semantics","Applied computing → Document preparation"]}}