Seam carving (or liquid rescaling) is an algorithm for content-aware image resizing, developed by Shai Avidan, of Mitsubishi Electric Research Laboratories (MERL), and Ariel Shamir, of the Interdisciplinary Center and MERL. It functions by establishing a number of seams (paths of least importance) in an image and automatically removes seams to reduce image size or inserts seams to extend it. Seam carving also allows manually defining areas in which pixels may not be modified, and features the ability to remove whole objects from photographs. The purpose of the algorithm is image retargeting, which is the problem of displaying images without distortion on media of various sizes (cell phones, projection screens) using document standards, like HTML, that already support dynamic changes in page layout and text but not images. Image Retargeting was invented by Vidya Setlur, Saeko Takage, Ramesh Raskar, Michael Gleicher and Bruce Gooch in 2005. The work by Setlur et al. won the 10-year impact award in 2015. == Seams == Seams can be either vertical or horizontal. A vertical seam is a path of pixels connected from top to bottom in an image with one pixel in each row. A horizontal seam is similar with the exception of the connection being from left to right. The importance/energy function values a pixel by measuring its contrast with its neighbor pixels. == Process == The below example describes the process of seam carving: The seams to remove depends only on the dimension (height or width) one wants to shrink. It is also possible to invert step 4 so the algorithm enlarges in one dimension by copying a low energy seam and averaging its pixels with its neighbors. === Computing seams === Computing a seam consists of finding a path of minimum energy cost from one end of the image to another. This can be done via Dijkstra's algorithm, dynamic programming, greedy algorithm or graph cuts among others. ==== Dynamic programming ==== Dynamic programming is a programming method that stores the results of sub-calculations in order to simplify calculating a more complex result. Dynamic programming can be used to compute seams. If attempting to compute a vertical seam (path) of lowest energy, for each pixel in a row we compute the energy of the current pixel plus the energy of one of the three possible pixels above it. The images below depict a DP process to compute one optimal seam. Each square represents a pixel, with the top-left value in red representing the energy value of that pixel. The value in black represents the cumulative sum of energies leading up to and including that pixel. The energy calculation is trivially parallelized for simple functions. The calculation of the DP array can also be parallelized with some interprocess communication. However, the problem of making multiple seams at the same time is harder for two reasons: the energy needs to be regenerated for each removal for correctness and simply tracing back multiple seams can form overlaps. Avidan 2007 computes all seams by removing each seam iteratively and storing an "index map" to record all the seams generated. The map holds a "nth seam" number for each pixel on the image, and can be used later for size adjustment. If one ignores both issues however, a greedy approximation for parallel seam carving is possible. To do so, one starts with the minimum-energy pixel at one end, and keep choosing the minimum energy path to the other end. The used pixels are marked so that they are not picked again. Local seams can also be computed for smaller parts of the image in parallel for a good approximation. == Issues == The algorithm may need user-provided information to reduce errors. This can consist of painting the regions which are to be preserved. With human faces it is possible to use face detection. Sometimes the algorithm, by removing a low energy seam, may end up inadvertently creating a seam of higher energy. The solution to this is to simulate a removal of a seam, and then check the energy delta to see if the energy increases (forward energy). If it does, prefer other seams instead. == Implementations == Adobe Systems acquired a non-exclusive license to seam carving technology from MERL, and implemented it as a feature in Photoshop CS4, where it is called Content Aware Scaling. As the license is non-exclusive, other popular computer graphics applications (e. g. GIMP, digiKam, and ImageMagick) as well as some stand-alone programs (e. g. iResizer) also have implementations of this technique, some of which are released as free and open source software. There also exists an implementation for webpages. == Improvements and extensions == Better energy function and application to video by introducing 2D (time+1D) seams. Faster implementation on GPU. Application of this forward energy function to static images. Multi-operator: Combine with cropping and scaling. Much faster removal of multiple seams. Removing seams through neural deformation fields to extend to continuous domains like 3D scenes. A 2010 review of eight image retargeting methods found that seam carving produced output that was ranked among the worst of the tested algorithms. It was, however, a part of one of the highest-ranking algorithms: the multi-operator extension mentioned above (combined with cropping and scaling).
Joint constraints
Joint constraints are rotational constraints on the joints of an artificial system. They are used in an inverse kinematics chain, in fields including 3D animation or robotics. Joint constraints can be implemented in a number of ways, but the most common method is to limit rotation about the X, Y and Z axis independently. An elbow, for instance, could be represented by limiting rotation on X and Z axis to 0 degrees, and constraining the Y-axis rotation to 130 degrees. To simulate joint constraints more accurately, dot-products can be used with an independent axis to repulse the child bones orientation from the unreachable axis. Limiting the orientation of the child bone to a border of vectors tangent to the surface of the joint, repulsing the child bone away from the border, can also be useful in the precise restriction of shoulder movement.
Menu hack
A menu hack is a non-standard method of ordering food, usually at fast-food or fast casual restaurants, that offers a different result than what is explicitly stated on a menu. Menu hacks may range from a simple alternate flavor to "gaming the system" in order to obtain more food than normal. They are often spread on social media platforms such as TikTok, and are more popular with Generation Z, which has been known to customize their orders more than previous generations. Hacks are sometimes officially added to the menu after their popularity grows. However, in some cases, they have been criticized for overburdening fast food employees with outlandish requests, sparking debate as to whether certain menu hacks are unethical. The list of all possible menu hacks is called a secret menu. == History == The term "menu hack" stems from hacker culture and its tradition of overcoming previously imposed limitations. However, the tradition of ordering from a secret menu dates back to the early days of fast food. "Animal style" fries, a word of mouth menu item ordered from In-N-Out since the 1960s, was rumored to have been created by local surfers. In the Information Age, the rise of social media gave influencers the ability to communicate unique food combinations to their followers, which proved to go viral easily. Design mistakes in food ordering apps also proved to be easily exploitable. In some cases, these hacks boosted the profile of brands on social media, while in others, they caused financial harm when the company was unprepared to handle the sudden influx of unusual orders. One restaurant chain notable for the phenomenon is Chipotle Mexican Grill. A viral hack from Alexis Frost, suggesting a quesadilla with fajita vegetables inside, dipped in Chipotle vinaigrette mixed with sour cream, obtained 1.9 million views on TikTok, overloading the chain's workers, who had to work harder to prepare more vegetables and vinaigrette. Some restaurants began to deny the dish to customers, forcing them to only order meat and cheese on quesadillas. The company ultimately left the dish on the menu, but urged customers to stop ordering it via social media. When it later officially added the Fajita Quesadilla to the menu, digital sales nearly doubled. A method to order nachos, which are not officially on the menu, was also noted by customers. Starbucks is also famous for menu hacks, including the Pink Drink, a "Barbiecore" beverage in which coconut milk replaced the water in the strawberry açaí refresher. After it went viral, the company made it a permanent menu item and distributed it bottled in grocery stores. == Controversy == Menu hacks have been subject to a growing backlash, with employees stating that they "dread" younger customers due to the proliferation of unusual orders. Service industry workers, already overworked and underpaid, have called the rise of menu hacks and their difficulty to make an additional reason to unionize and demand higher wages.
Chunked transfer encoding
Chunked transfer encoding is a streaming data transfer mechanism available in Hypertext Transfer Protocol (HTTP) version 1.1, defined in RFC 9112 §7.1. In chunked transfer encoding, the data stream is divided into a series of non-overlapping "chunks". The chunks are sent out and received independently of one another. At any given time, no knowledge of the data stream outside the currently-being-processed chunk is necessary for either the sender or the receiver. Each chunk is preceded by its size in bytes and transmission ends when a zero-length chunk is received. The chunked keyword in the Transfer-Encoding header is used to indicate chunked transfer. Chunked transfer encoding is not supported in HTTP/2, which provides its own mechanisms for data streaming. == Rationale == The introduction of chunked encoding provided various benefits: Chunked transfer encoding allows a server to maintain an HTTP persistent connection for dynamically generated content. In this case, the HTTP Content-Length header cannot be used to delimit the content and the next HTTP request/response, as the content size is not yet known. Chunked encoding has the benefit that it is not necessary to generate the full content before writing the header, as it allows streaming of content as chunks and explicitly signaling the end of the content, making the connection available for the next HTTP request/response. Chunked encoding allows the sender to send additional header fields after the message body. This is important in cases where values of a field cannot be known until the content has been produced, such as when the content of the message must be digitally signed. Without chunked encoding, the sender would have to buffer the content until it was complete in order to calculate a field value and send it before the content. == Applicability == For version 1.1 of the HTTP protocol, the chunked transfer mechanism is considered to be always and anyway acceptable, even if not listed in the Transfer-Encoding (TE) request header field, and when used with other transfer mechanisms, should always be applied last to the transferred data and never more than one time. This transfer encoding method also allows additional entity header fields to be sent after the last chunk if the client specified the "trailers" parameter as an argument of the TE request field. The origin server of the response can also decide to send additional entity trailers even if the client did not specify the "trailers" parameter, but only if the metadata is optional (i.e. the client can use the received entity without them). Whenever the trailers are used, the server should list their names in the Trailer header field; three header field types are specifically prohibited from appearing as a trailer field: Content-Length, Trailer, and Transfer-Encoding. == Format == If a Transfer-Encoding field with a value of "chunked" is specified in an HTTP message (either a request sent by a client or the response from the server), the body of the message consists of one or more chunks and one terminating chunk with an optional trailer before the final ␍␊ sequence (i.e. carriage return followed by line feed). Each chunk starts with the number of octets of the data it embeds expressed as a hexadecimal number in ASCII followed by optional parameters (chunk extension) and a terminating ␍␊ sequence, followed by the chunk data. The chunk is terminated by ␍␊. If chunk extensions are provided, the chunk size is terminated by a semicolon and followed by the parameters, each also delimited by semicolons. Each parameter is encoded as an extension name followed by an optional equal sign and value. These parameters could be used for a running message digest or digital signature, or to indicate an estimated transfer progress, for instance. The terminating chunk is a special chunk of zero length. It may contain a trailer, which consists of a (possibly empty) sequence of entity header fields. Normally, such header fields would be sent in the message's header; however, it may be more efficient to determine them after processing the entire message entity. In that case, it is useful to send those headers in the trailer. Header fields that regulate the use of trailers are Transfer-Encoding with the "trailers" parameter (used in requests) and Trailer (used in responses). == Use with compression == HTTP servers often use compression to optimize transmission, for example with Content-Encoding: gzip or Content-Encoding: deflate. If both compression and chunked encoding are enabled, then the content stream is first compressed, then chunked; so the chunk encoding itself is not compressed, and the data in each chunk is compressed holistically (i.e. based on the whole content). The remote endpoint then decodes the stream by concatenating the chunks and uncompressing the result. == Example == === Encoded data === The following example contains three chunks of size 4, 7, and 11 (hexadecimal "B") octets of data. 4␍␊Wiki␍␊7␍␊pedia i␍␊B␍␊n ␍␊chunks.␍␊0␍␊␍␊ Below is an annotated version of the encoded data. 4␍␊ (chunk size is four octets) Wiki (four octets of data) ␍␊ (end of chunk) 7␍␊ (chunk size is seven octets) pedia i (seven octets of data) ␍␊ (end of chunk) B␍␊ (chunk size is eleven octets) n ␍␊chunks. (eleven octets of data) ␍␊ (end of chunk) 0␍␊ (chunk size is zero octets, no more chunks) ␍␊ (end of final chunk with zero data octets) Note: Each chunk's size excludes the two ␍␊ bytes that terminate the data of each chunk. === Decoded data === Decoding the above example produces the following octets: Wikipedia in ␍␊chunks. The bytes above are typically displayed as Wikipedia in chunks.
Factorization of polynomials over finite fields
In mathematics and computer algebra the factorization of a polynomial consists of decomposing it into a product of irreducible factors. This decomposition is theoretically possible and is unique for polynomials with coefficients in any field, but rather strong restrictions on the field of the coefficients are needed to allow the computation of the factorization by means of an algorithm. In practice, algorithms have been designed only for polynomials with coefficients in a finite field, in the field of rationals or in a finitely generated field extension of one of them. All factorization algorithms, including the case of multivariate polynomials over the rational numbers, reduce the problem to this case; see polynomial factorization. It is also used for various applications of finite fields, such as coding theory (cyclic redundancy codes and BCH codes), cryptography (public key cryptography by the means of elliptic curves), and computational number theory. As the reduction of the factorization of multivariate polynomials to that of univariate polynomials does not have any specificity in the case of coefficients in a finite field, only polynomials with one variable are considered in this article. == Background == === Finite field === The theory of finite fields, whose origins can be traced back to the works of Gauss and Galois, has played a part in various branches of mathematics. Due to the applicability of the concept in other topics of mathematics and sciences like computer science there has been a resurgence of interest in finite fields and this is partly due to important applications in coding theory and cryptography. Applications of finite fields introduce some of these developments in cryptography, computer algebra and coding theory. A finite field or Galois field is a field with a finite order (number of elements). The order of a finite field is always a prime or a power of prime. For each prime power q = pr, there exists exactly one finite field with q elements, up to isomorphism. This field is denoted GF(q) or Fq. If p is prime, GF(p) is the prime field of order p; it is the field of residue classes modulo p, and its p elements are denoted 0, 1, ..., p−1. Thus a = b in GF(p) means the same as a ≡ b (mod p). === Irreducible polynomials === Let F be a finite field. As for general fields, a non-constant polynomial f in F[x] is said to be irreducible over F if it is not the product of two polynomials of positive degree. A polynomial of positive degree that is not irreducible over F is called reducible over F. Irreducible polynomials allow us to construct the finite fields of non-prime order. In fact, for a prime power q, let Fq be the finite field with q elements, unique up to isomorphism. A polynomial f of degree n greater than one, which is irreducible over Fq, defines a field extension of degree n which is isomorphic to the field with qn elements: the elements of this extension are the polynomials of degree lower than n; addition, subtraction and multiplication by an element of Fq are those of the polynomials; the product of two elements is the remainder of the division by f of their product as polynomials; the inverse of an element may be computed by the extended GCD algorithm (see Arithmetic of algebraic extensions). It follows that, to compute in a finite field of non prime order, one needs to generate an irreducible polynomial. For this, the common method is to take a polynomial at random and test it for irreducibility. For sake of efficiency of the multiplication in the field, it is usual to search for polynomials of the shape xn + ax + b. Irreducible polynomials over finite fields are also useful for pseudorandom number generators using feedback shift registers and discrete logarithm over F2n. The number of irreducible monic polynomials of degree n over Fq is the number of aperiodic necklaces, given by Moreau's necklace-counting function Mq(n). The closely related necklace function Nq(n) counts monic polynomials of degree n which are primary (a power of an irreducible); or alternatively irreducible polynomials of all degrees d which divide n. === Example === The polynomial P = x4 + 1 is irreducible over Q but not over any finite field. On any field extension of F2, P = (x + 1)4. On every other finite field, at least one of −1, 2 and −2 is a square, because the product of two non-squares is a square and so we have If − 1 = a 2 , {\displaystyle -1=a^{2},} then P = ( x 2 + a ) ( x 2 − a ) . {\displaystyle P=(x^{2}+a)(x^{2}-a).} If 2 = b 2 , {\displaystyle 2=b^{2},} then P = ( x 2 + b x + 1 ) ( x 2 − b x + 1 ) . {\displaystyle P=(x^{2}+bx+1)(x^{2}-bx+1).} If − 2 = c 2 , {\displaystyle -2=c^{2},} then P = ( x 2 + c x − 1 ) ( x 2 − c x − 1 ) . {\displaystyle P=(x^{2}+cx-1)(x^{2}-cx-1).} === Complexity === Polynomial factoring algorithms use basic polynomial operations such as products, divisions, gcd, powers of one polynomial modulo another, etc. A multiplication of two polynomials of degree at most n can be done in O(n2) operations in Fq using "classical" arithmetic, or in O(nlog(n) log(log(n)) ) operations in Fq using "fast" arithmetic. A Euclidean division (division with remainder) can be performed within the same time bounds. The cost of a polynomial greatest common divisor between two polynomials of degree at most n can be taken as O(n2) operations in Fq using classical methods, or as O(nlog2(n) log(log(n)) ) operations in Fq using fast methods. For polynomials h, g of degree at most n, the exponentiation hq mod g can be done with O(log(q)) polynomial products, using exponentiation by squaring method, that is O(n2log(q)) operations in Fq using classical methods, or O(nlog(q)log(n) log(log(n))) operations in Fq using fast methods. In the algorithms that follow, the complexities are expressed in terms of number of arithmetic operations in Fq, using classical algorithms for the arithmetic of polynomials. == Factoring algorithms == Many algorithms for factoring polynomials over finite fields include the following three stages: Square-free factorization Distinct-degree factorization Equal-degree factorization An important exception is Berlekamp's algorithm, which combines stages 2 and 3. === Berlekamp's algorithm === Berlekamp's algorithm is historically important as being the first factorization algorithm which works well in practice. However, it contains a loop on the elements of the ground field, which implies that it is practicable only over small finite fields. For a fixed ground field, its time complexity is polynomial, but, for general ground fields, the complexity is exponential in the size of the ground field. === Square-free factorization === The algorithm determines a square-free factorization for polynomials whose coefficients come from the finite field Fq of order q = pm with p a prime. This algorithm firstly determines the derivative and then computes the gcd of the polynomial and its derivative. If it is not one then the gcd is again divided into the original polynomial, provided that the derivative is not zero (a case that exists for non-constant polynomials defined over finite fields). This algorithm uses the fact that, if the derivative of a polynomial is zero, then it is a polynomial in xp, which is, if the coefficients belong to Fp, the pth power of the polynomial obtained by substituting x by x1/p. If the coefficients do not belong to Fp, the pth root of a polynomial with zero derivative is obtained by the same substitution on x, completed by applying the inverse of the Frobenius automorphism to the coefficients. This algorithm works also over a field of characteristic zero, with the only difference that it never enters in the blocks of instructions where pth roots are computed. However, in this case, Yun's algorithm is much more efficient because it computes the greatest common divisors of polynomials of lower degrees. A consequence is that, when factoring a polynomial over the integers, the algorithm which follows is not used: one first computes the square-free factorization over the integers, and to factor the resulting polynomials, one chooses a p such that they remain square-free modulo p. Algorithm: SFF (Square-Free Factorization) Input: A monic polynomial f in Fq[x] where q = pm Output: Square-free factorization of f R ← 1 # Make w be the product (without multiplicity) of all factors of f that have # multiplicity not divisible by p c ← gcd(f, f′) w ← f/c # Step 1: Identify all factors in w i ← 1 while w ≠ 1 do y ← gcd(w, c) fac ← w / y R ← R · faci w ← y; c ← c / y; i ← i + 1 end while # c is now the product (with multiplicity) of the remaining factors of f # Step 2: Identify all remaining factors using recursion # Note that these are the factors of f that have multiplicity divisible by p if c ≠ 1 then c ← c1/p R ← R·SFF(c)p end if Output(R) The idea is to identify the product of all irreducible factors of f with the same multiplicity. This is done in two steps. The first step uses the formal d
STIT logic
STIT logic (from seeing to it that) is a family of modal and branching-time logics for reasoning about agency and choice. A typical STIT operator has the form [ i s t i t : φ ] {\displaystyle [i\ {\mathsf {stit}}:\varphi ]} , usually read as "agent i {\displaystyle i} sees to it that φ {\displaystyle \varphi } ", and is interpreted in models where agents choose between alternative possible futures. STIT logics are used in action theory, deontic logic, epistemic logic, and the theory of intelligent agents to formalise notions such as "could have done otherwise", responsibility, joint action, and strategic ability in an indeterministic world. == Etymology == The acronym STIT comes from the English phrase "seeing to it that", introduced in influential work by Nuel Belnap and Michael Perloff on the logical analysis of agentive expressions. In this tradition, "to see to it that φ {\displaystyle \varphi } " is treated as a primitive agency operator, rather than being reduced to ordinary modal necessity. == History == Modern STIT logic arose in the 1980s in the context of branching-time semantics and formal theories of agency. Belnap and Perloff's article "Seeing to it that: A canonical form for agentives" introduced the idea of treating expressions of the form "agent i sees to it that φ" as a primitive modal operator, and analysed such sentences using a branching tree of moments and histories. This approach was further developed in a series of papers on indeterminism and agency and provided the conceptual core for later STIT formalisms. In the 1990s the basic formal systems of STIT logic were worked out. Horty and Belnap's influential paper on the deliberative STIT operator distinguished between a "Chellas" STIT that merely records the result of an agent's present choice and a "deliberative" STIT that requires the agent's choice to make a difference, and connected STIT with issues of action, omission, ability and obligation. Around the same time, Ming Xu proved completeness and decidability results for basic STIT systems, including a single-agent logic with Kripke-style semantics and axiomatizations for multi-agent deliberative STIT, thereby establishing STIT as a well-behaved normal modal framework. This early work was systematised in Belnap, Perloff and Xu's monograph Facing the Future: Agents and Choices in Our Indeterminist World, which presents a general branching-time semantics for individual and group STIT operators, discusses independence-of-agents conditions and articulates the metaphysical picture of an indeterministic "tree" of moments. At roughly the same time, Horty's book Agency and Deontic Logic developed deontic STIT logics in which obligations are tied to agents' available choices rather than to static states of affairs, and used the resulting systems to analyse "ought implies can", contrary-to-duty obligations and deontic paradoxes. These works helped to position STIT at the intersection of action theory, temporal logic and deontic logic. From the late 1990s and 2000s onward, STIT logics were combined with epistemic, temporal and strategic modalities. Broersen introduced complete STIT logics for knowledge and action and deontic-epistemic STIT systems that distinguish different modes of mens rea, with applications to responsibility and the specification of multi-agent systems. Work on group and coalitional agency investigated axiomatisations and complexity results for group STIT logics, and related STIT-based analyses of agency to coalition logic and alternating-time temporal logic (ATL) by exhibiting formal embeddings between the frameworks. Explicit temporal operators were added to STIT in so-called temporal STIT logics. Lorini proposed a temporal STIT with "next" and "until" operators along histories and showed how it can be applied to normative reasoning about ongoing behaviour and commitments. Ciuni and Lorini compared different semantics for temporal STIT, clarifying the relationships between branching-time, game-based and epistemic approaches, while Boudou and Lorini gave a semantics for temporal STIT based on concurrent game structures, thus strengthening links with standard models of multi-agent interaction used for ATL and strategy logic. In parallel, complexity-theoretic work by Balbiani, Herzig and Troquard and by Schwarzentruber and co-authors investigated the satisfiability and model-checking problems for various STIT fragments, showing for instance that many expressive group STIT logics are undecidable or of high computational complexity. In the 2010s, STIT ideas were combined with justification logic, imagination operators and refined deontic notions. Justification STIT logics, developed by Olkhovikov and others, merge explicit justifications with STIT-style agency so that producing a proof can itself be treated as an action that brings about knowledge, and they come with completeness and decidability results. Olkhovikov and Wansing introduced STIT imagination logics, together with axiomatic systems and tableau calculi, to model acts of voluntary imagining and their role in doxastic control. Other authors have proposed STIT-based logics of responsibility, blameworthiness and intentionality for use in philosophical and AI settings. Xu's survey article "Combinations of STIT with Ought and Know" (2015) reviews many of these developments and emphasises the interplay between deontic and epistemic STIT logics. Current research on STIT focuses on proof theory, automated reasoning and richer expressive resources. Lyon and van Berkel, building on earlier work on labelled calculi for STIT, have developed cut-free sequent systems and proof-search algorithms that yield syntactic decision procedures for a range of deontic and non-deontic multi-agent STIT logics and support applications such as duty checking and compliance checking in autonomous systems. Sawasaki has proposed first-order cstit-based STIT logics that can distinguish de re and de dicto readings of agency statements and has proved strong completeness results for Hilbert systems over finite models, moving the STIT programme beyond the purely propositional level. Further work investigates interpreted-system and computationally grounded semantics for STIT and its extensions in order to model the behaviour of autonomous agents in multi-agent settings, and proposes STIT-based semantics for epistemic notions based on patterns of information disclosure in interactive systems. == Branching-time semantics == STIT logics are usually interpreted over branching-time models. A standard STIT frame consists of: a non-empty set of moments T {\displaystyle T} , partially ordered by < {\displaystyle <} so that ( T , < ) {\displaystyle (T,<)} forms a tree (every pair of moments with a common predecessor has a greatest lower bound); a set of histories, each history being a maximal linearly ordered subset of T {\displaystyle T} ; a non-empty set of agents A g {\displaystyle Ag} ; for each agent i ∈ A g {\displaystyle i\in Ag} and moment m {\displaystyle m} , a choice function c h o i c e i m {\displaystyle {\mathsf {choice}}_{i}^{m}} that partitions the set of histories passing through m {\displaystyle m} into choice cells. The idea is that a moment represents a time at which choices are made, and histories represent complete possible future courses of events. At each moment, each agent's choice corresponds to selecting one of the available cells of histories determined by their choice function. Formulas are evaluated at pairs ( m , h ) {\displaystyle (m,h)} of a moment and a history through that moment (sometimes written m / h {\displaystyle m/h} ). A valuation assigns truth-values to atomic propositions at such indices; Boolean connectives are interpreted pointwise as in Kripke-style modal logic. == Chellas and deliberative STIT operators == Several STIT operators have been distinguished in the literature. A common approach uses two closely related operators, often called Chellas STIT and deliberative STIT. Let H m {\displaystyle H_{m}} be the set of histories passing through a moment m {\displaystyle m} , and write H m {\displaystyle H_{m}} ⟦ φ ⟧ m = { h ∈ H m ∣ M , m / h ⊨ φ } {\displaystyle {\text{⟦}}\varphi {\text{⟧}}_{m}=\{h\in H_{m}\mid M,m/h\models \varphi \}} for the set of histories at m {\displaystyle m} where φ {\displaystyle \varphi } holds. The Chellas STIT operator, often written [ i c s t i t : φ ] {\displaystyle [i\ {\mathsf {cstit}}:\varphi ]} , is given by M , m / h ⊨ [ i c s t i t : φ ] iff c h o i c e i m ( h ) ⊆ ⟦ φ ⟧ m . {\displaystyle M,m/h\models [i\ {\mathsf {cstit}}:\varphi ]\quad {\text{iff}}\quad {\mathsf {choice}}_{i}^{m}(h)\subseteq {\text{⟦}}\varphi {\text{⟧}}_{m}.} Intuitively, agent i {\displaystyle i} sees to it that φ {\displaystyle \varphi } if φ {\displaystyle \varphi } holds at all histories compatible with their present choice. The deliberative STIT operator, [ i d s t i t : φ ] {\displaystyle [i\ {\mathsf {dstit}}:\varphi ]} , adds
Blocknots
Blocknots were random sequences of numbers contained in a book and organized by numbered rows and columns and were used as additives in the reciphering of Soviet Union codes, during World War II. The Blocknot consisted of a booklet of fifty sheets of 5-figure random additive, 100 additive groups to a sheet. No sheet was used more than once, thus the blocknots were in effect a form of one-time pad. The Soviet Unions highest grade ciphers that were used in the East, were the 5-figure codebook enciphered with the Blocknot book, and were generally considered unbreakable. == Technical Description == Blocknots were distributed centrally from an office in Moscow. Every Blocknot contained 5-figure groups in a number of sheets, for the enciphering of 5-figure messages. The encipherment was effected by applying additives taken from the pad, of which 50-100 5-figure groups appeared. Each pad had a 5-figure number and each sheet had a 2-figure number running consecutively. There were 5 different types of Blocknots, in two different categories The Individual in which each table of random numbers was used only once. The General in which each page of the Blocknot was valid for one day. The security of the additive sequence rested on the choice of different starting points for each message. In 5-figure messages, the blocknot was one of the first 10 Groups in the message. Its position changed at long intervals, but was always easy to re-identify. The Russians differentiated between three types of blocks: The 3-block, DRIERBLOCK. I-block for Individual Block: 50 pages, additive read off in one direction only. The messages could be used and read only between 2 wireless telegraphy stations on one net. The 6-block, SECHSERBLOCK. Z-block for Circular Block: 30 pages, additive read off in either direction. The messages could be used and read, between all W/T stations in a net. The 2-block, ZWEIERBLOCK. OS-block. Used only in traffic from lower to higher formations. Two other types were used, in lower echelons. Notblock: Used in an emergency. Blocknot used for passing on traffic. The distribution of Blocknots was carried out centrally from Moscow to Army Groups then to Armies. The Army was responsible for their distribution throughout the lower levels of the army down to company level. Independent units took their cipher material with them. Occasionally the same blocknot was distributed to two units on different parts of the front, which enabled Depth to be established. Records of all Blocknots used were kept in Berlin and when a repeat was noticed a BLOCKNOT ANGEBOT message was sent out to all German Signals units, to indicate that it may have been possible to break the code using it. There was no certainty in this. A cryptanalyst with the General der Nachrichtenaufklärung stated while being interrogated by TICOM: It seems that depths of up to 8 were established at the beginning of the Russian Campaign but that no 5-figure code was broken after May 1943 German cryptanalysts who were prisoners of war stated under interrogation, that each of the figures 0 to 9 were placed en clair usually within the first ten groups of the text or sometimes at the end. One indicator was the Blocknot number and the consisted of two random figures, the figure representing the type, and the remaining two, the page of the Blocknot being used. In long messages, 000000 was placed in the message when the end of a page had been reached. == Chi number == The Chi-number was the serial numbering of all 5-figure messages passing through the hands of the Cipher Officer, starting on the first of January and ending on thirty-first December of the current year. It always appeared as the last group in an intercepted message, e.g. 00001 on the 1st January, or when the unit was newly set up. The progression of Chi-numbers was carefully observed and recorded in the form of a graph. A Russian corps had about 10 5-figure messages per day, and Army about 20-30 and a Front about 60–100. After only a relatively short time, the individual curves separated sharply and the type of formation could be recognized by the height of the Chi-number alone. == Monitoring == Blocknots were tracked in a card index, that was maintained by the Signal Intelligence Evaluation Centre (NAAS). The NAAS functionality included evaluation and traffic analysis, cryptanalysis, collation and dissemination of intelligence. The card index, which was one amongst several Card Indexes. A careful recording and study of blocks provided the positive clues in the identification and tracking of formations using 5-figure ciphers. The index was subdivided into two files: Search card index, contained all blocknots and chi-numbers whether or not they were known. Unit card index, contained only known Block and Chi-numbers. Inspector Berger, who was the chief cryptanalyst of NAAS 1 stated that the two files formed: The most important and surest instruments for identifying Russian radio nets, known to him. The Blocknots were also used in the Stationary Intercept Company (Feste), the military unit that were designed to work at a lower level to the NAAS, at the Army level and were semi-motorized, and closer to the front. The Feste used the Blocknot value along with several other parameters to build a network diagram. The network diagram was studied extensively, as part of a 6-stage process, that involved several departments within the Feste. The outcome was a metric which determined the most interesting circuit for traffic monitoring, and least interesting, where monitoring of traffic should cease. == Analysis == Johannes Marquart was a mathematician and cryptanalyst who initially worked for Inspectorate 7/VI and later led Referat Ia of Group IV of the General der Nachrichtenaufklärung. Marquart was assigned the study of the Soviet Union Blocknot traffic. Marquart and his unit conducted extensive research in an attempt to discover the method by which they were produced. All the counts which they made, however, failed to reveal any non-random characteristics in the design of the tables, and while they thought the Blocknots must have been generated by machine, they were never able to draw any concrete deductions as a result of their research. == Example == The Soviet 3rd Guard Tank Army transmits a 5-figure message with the Blocknot of 37581 (one of the first 10 groups in the message). On the same day the Block 37582 was used by the same formation. The next day 37583 appeared. Thereafter, for a period, the Army was not heard by German Wireless telegraphy intercept operators, as it was maintaining wireless silence. After a few days, an unidentified net with the Blocknot 37588 is picked up. This message net is claimed, because of the proximity of the blocks (88/83) to be the 3rd Guard Tank Army. The missing Blocknots 84-87 were presumably used in telegraphic, telephonic or courier communications. The Chi number provides confirmation of the first assumption, based on proximity of blocknots in most cases.