Expected execution times for the limit EUR/USD orders in the global FX spot market are presented. The execution time estimates are given for different order sizes and for varying distances between the order price and the market best price. These results are used in a simple value-at-risk based theory for trading large amounts by slicing them into smaller orders. Finally, the current discussion of the long-memory order flows in equity markets is expanded into the global FX market.

The order life time at the top of the order book is defined as the time between the order arrival at the top of the order book and its removal from the top of the order book. In this work, the average order life time in the EBS FX spot market is analyzed for two corresponding four-week periods in 2004 and 2005. The following currency pairs, EUR/USD, USD/JPY, USD/CHF, EUR/JPY, and EUR/CHF, are considered during the most liquid period of the working day, 7:00 – 17:00 GMT. Generally, the distribution of orders with a given life time at the top of the order book decays exponentially at short times. However this decay follows a power law at longer time periods. The crossover times between the two decay forms are estimated. It is shown that the decays have steepened and the order life time has become shorter in 2005. In particular, 47.9% of the EUR/USD orders and 34.7% of the USD/JPY orders live less than one second on the top of the order book. Two possible causes of the power-law asymptote are indicated: orders with amounts significantly higher than the average value and the specifics of credit relations among the EBS customers. The only exclusion from the described pattern is the order dynamics of EUR/CHF in 2005 that does not have an exponential decay.

This paper studies the transmission of volatility and trading activity in the foreign exchange market across trading regions for the euro-dollar and dollar-yen currency pairs, using high-frequency intraday data from Electronic Broking Services (EBS). In contrast with previous studies that use indicative quote frequency to proxy for trading activity, we use actual regional trading volume to identify five distinct trading regions in the foreign exchange market: Asia Pacific, the Asia-Europe overlap, Europe, the Europe-America overlap, and America. Based on realized volatility computed from high-frequency data and a regional volatility model, we find statistically significant evidence for volatility spillovers at both the own-region and the inter-region levels, but the economic significance of own-region spillovers is much more important than that of inter-region spillovers. We also examine the transmission of trading activity (trading volume and number of transactions) across the five trading regions and find similar results to those for volatility, but the economic significance of own-region spillovers is even more dominant.

We analyze the factors driving the widely-noted persistence in asset return volatility using a unique dataset on global euro-dollar exchange rate trading. We propose a new simple empirical specification of volatility, based on the Kyle-model, which links volatility to the information flow, measured as the order flow in the market, and the price sensitivity to that information. Through the use of high-frequency data, we are able to estimate the time-varying market sensitivity to information, and movements in volatility can therefore be directly related to movements in two observable variables, the order flow and the market sensitivity. The empirical results are very strong and show that the model is able to explain almost all of the long-run variation in volatility. Our results also show that the variation over time of the market’s sensitivity to information plays at least as important a role in explaining the persistence of volatility as does the rate of information arrival itself. The econometric analysis is conducted using novel estimation techniques which explicitly take into account the persistent nature of the variables and allow us to properly test for long-run relationships in the data.

We analyze the association between order flow and exchange rates using a new dataset representing a majority of global interdealer transactions in the two most-traded currency pairs. The data consist of six years (1999-2004) of order flow and exchange rate data for the euro-dollar and dollar-yen currency pairs at the one-minute frequency from EBS, the electronic broking system that now dominates interdealer spot trading in these currency pairs. This long span of high-frequency data allows us to gain new insights about the joint behavior of these series. We first confirm the presence of a substantial association between interdealer order flow and exchange rate returns at frequencies ranging from one minute to one week, but, using our long span of data, we find that the association is weaker at lower frequencies, with far less long-term association between cumulative order flow and long-term exchange rate movements. We study the linearity and time-variation of the association between high-frequency exchange rate returns and order flow, and document an intradaily pattern to the relationship: it is weakest at times when markets are most active. Overall, our study tends to support the view that, while order flow plays a crucial role in high-frequency exchange rate movements, its role in driving long-term fluctuations is much more limited.

We introduce a new high-frequency foreign exchange dataset from EBS (Electronic Broking Service) that includes trading volume in the global interdealer spot market, data not previously available to researchers. The data also gives live transactable quotes, rather than the indicative quotes that have been used in most previous high frequency foreign exchange analysis. We describe intraday volume and volatility patterns in euro-dollar and dollar-yen trading. We study the effects of scheduled U.S. macroeconomic data releases, first confirming the finding of recent literature that the conditional mean of the exchange rate responds very quickly to the unexpected component of data releases. We next study the effects of data releases on trading volumes. News releases cause volume to rise, and to remain elevated for a longer period. However, in contrast to the result for the level of the exchange rate, even if the data release is entirely in line with expectations, we find that there is still typically a large pickup in trading volume.

Clog Prolog is a Prolog interpreter running under Waltz LISP. The chief reason for creating Clog was to provide an easily modifiable Prolog interpreter for the benefit of people interested in logic programming. Another purpose of Clog is to serve as an example of a non-trivial application program written in Waltz LISP. In about 200 lines of Waltz LISP code Clog implements fully the logical core and the main functions of the Prolog language. In addition, Clog has complete access to all of the facilities of the Waltz LISP system, which endows Clog with more practical utilities than what is found in many major Prolog implementations. A large number of Prolog interpreters has now been written in LISP, although the first (“Marseille”) Prolog interpreter (Battani and Meloni, 1973) was written in Prolog (bootstrapped from FORTRAN). Several such interpreters are described in “Implementations of Prolog” (ed. J. A. Campbell, John Wiley & Sons 1984). Clog was inspired by M. Nilsson’s implementation included in that volume (“The World’s Shortest Prolog Interpreter?”, pp. 87-92). On a more fundamental level, the concept of structure sharing used in this implementation is due to R. S. Boyer and J. Moore (“The sharing of structure in theorem proving programs”, Machine Intelligence 7, 1972). These notes are more than a reference manual, yet less than a full Prolog tutorial. Hopefully, the reader will glimpse enough of Prolog to decide whether to look at the language in more detail.

Waltz LISP is a powerful and complete implementation of the LISP programming language for PC-DOS/MS-DOS and CP/M-80 computers. Its more than 250 functions include many found only in large mainframe LISPs. In fact, Waltz LISP is substantially compatible with Franz LISP, the LISP running under Unix. It is also similar to Common LISP, LISP Machine LISP, and MacLISP. Waltz LISP is a perfect language for Artificial Intelligence programming. Like most large LISPs, Waltz has a complete suite of mappers, built-in prettyprinting and level printing, fast sort and merge, I/O streams (devices), and advanced program control structures (do, let, catch, throw, etc.). It also supports functions of type lambda (expr), nlambda (fexpr), lexpr, macro, and both splicing and non-splicing character read macros. The interpreted nature of the language and excellent debugging and error handling facilities speed up the program development without sacrificing the elegant structure or clarity of the code. In short, Waltz has all the features necessary for serious AI programming. Clog Prolog, a small but complete implementation of Prolog in Waltz LISP, is available as an example of Waltz LISP’s ability to handle complex applications.

Waltz is unique among microcomputer LISPs in that it is also suitable for general applications. Its powerful operating system interface, random file access, and ability to handle textual and other non-LISP data with ease make writing general purpose utilities easy. In fact, it is often easier to write a utility program in Waltz LISP than in any other programming language. Much faster than competing microcomputer LISP interpreters. Uses a very fast non-recursive (stackless) automatic garbage collector that may also be called explicitly by the user’s program. A built-in full-screen editor permits editing files of any size from within the LISP environment. Full implementation of long integers (up to 611 decimal digits) with user-selectable radix. True dynamic character strings with a complete set of string operations including concatenation, substring extraction, alphabetic case conversion, and sophisticated pattern matching functions.

A connected graph G is ptolemaic provided that for each four vertices u_i, 1 ≤ i ≤ 4, of G, the six distances d_ij = d_G (u_i, u_j), i ≠ j satisfy the inequality d₁₂d₃₄ ≤ d₁₃d₂₄ + d₁₄d₂₃ (shown by Ptolemy to hold in Euclidean spaces). Ptolemaic graphs were first investigated by Chartrand and Kay, who showed that weakly geodetic ptolemaic graphs are precisely Husimi trees (in particular, trees are ptolemaic). In the present paper several characterizations of ptolemaic graphs are given. It is shown, for example, that a connected graph G is ptolemaic if and only if for each nondisjoint cliques P, Q of G, their intersection is a cutset of G which separates P-Q and Q-P. An operation is exhibited which generates all finite ptolemaic graphs from complete graphs.

The distance d_G(u,v) between vertices u, v of a graph G is the least number of edges in any u-v path of G; d_G(u,v) = ∞ if u and v lie in distinct components of G. A graph G = (V,E) is distance-critical, if for each x∈V there are vertices u, v (depending on x) such that d_G(u,v) < d_G-x(u,v). Let g(n) denote the largest integer such that |E| ≤ C(n,2) – g(n) for every distance-critical graph on n vertices. It follows from the results of this note that g(n) is of the order of magnitude of n^3/2; possibly, one has g(n) ∼ √2 n^3/2.

This work studies classes of graphs G defined by conditions imposed on the metric or betweenness space associated with G. It is shown that the class of integer-valued metric spaces realizable in Husimi trees is characterized by a classical condition used often to characterize the tree-realizable metric spaces, the so-called four-point condition. Several other metric conditions satisfied by trees are considered, and the corresponding classes of graphs characterized. Distance-hereditary graphs (graphs G whose connected induced subgraphs preserve the distance of G) are described in terms of their cycle and clique structure. Ptolemaic graphs (graphs whose associated metric space is ptolemaic) are shown to be distance-hereditary. Several characterizations of ptolemaic graphs are given, and the operation is exhibited which generates all finite ptolemaic graphs from complete graphs.

Modular graphs (graphs where every triple of vertices is contained in a distance-preserving subtree) are investigated; this leads to study of abstract (ternary) betweenness relations. A new notion, l-modular betweenness, is introduced and shown to generalize in a remarkable way the notion of median betweenness. Betweenness relations arising from graphs are studied; those arising from bipartite graphs are efficiently characterized. The results on betweenness relations are specialized and used to characterize modular, and related, graphs. As an application, a very general (assuming no preexisting orientation) characterization of graphs of modular and distributive lattices is obtained. Several open problems and an extensive bibliography are included.

The paper provides a unified point of view on some classes of graphs: clique graphs, weakly geodetic graphs, ptolemaic graphs and Husimi trees. A purely metric characterization of Husimi trees is given.

Let G be an infinite graph; define deg_∞G to be the least m such that any partition P of the vertex set of G into sets of uniformly bounded cardinality contains a set which is adjacent to at least m other sets of the partition. If G is either a regular tree or a triangular, square or hexagonal planar mosaic graph, it is shown that deg_∞G equals the degree of G. This verifies some conjectures of S. Ulam. Several open problems are given.

The graphs considered are undirected, without loops or multiple edges. The distance d_G(u,v) between two vertices u, v of a connected graph G is the length of a shortest u-v path of G. (V(G), d_G) is the metric space associated with G. The present note deals with graphs whose metric structure is hereditary in the following sense: A graph G is called distance-hereditary if each connected induced subgraph F of G has the property that d_F(u,v) = d_G(u,v), for each u, v∈F. In other words, we require that, whenever F is a connected induced subgraph of G, then (V(F), d_F) is a metric subspace of (V(C), d_C), where C is the component of G containing F. Distance-hereditary graphs are completely characterized in the main theorem. A theorem due to E. Olaru and H. Sachs is then applied to deduce that distance-hereditary graphs are perfect.

A metric space G is ptolemaic if for each four elements u_i, 1 ≤ i ≤ 4, of X, the six distances d_ij = d(u_i, u_j), i ≠ j satisfy the inequality d₁₂d₃₄ ≤ d₁₃d₂₄ + d₁₄d₂₃ (shown by Ptolemy to hold in Euclidean spaces). The notion of ptolemaic space was introduced by L. M. Blumenthal (1943). G. Chartrand and D. C. Kay (1965) defined ptolemaic graphs: A graph G is ptolemaic if G is connected and if the associated metric space (V(G),d_G) is ptolemaic. It is known that the only graphs which can be isometrically embedded in a Euclidean space are open paths and finite complete graphs–a narrow class indeed. The ptolemaic inequality may be regarded, therefore, as a naturally weaker condition which nevertheless preserves certain remarkable geometric properties of the Euclidean distance. In the present paper a detailed description of ptolemaic graphs is given. No proofs are included. Whenever it is relevant, we show the relationship between ptolemaic graphs and other classes of graphs.

We survey the results on existence of universal graphs and pose an open problem: Does there exist a countable graph H which is universal for isometric embedding, that is, for every countable graph G, there is an embedding f: V(G)→V(H) such that d_G(u,v) = d_H(f(u),f(v)) for every u,v∈V(G).

Ed: Shown to be true by J. Pach, On metric properties of countable graphs, Mat Lapok 26.

Let B_n denote the collection of all binary relations on the set X = {1,2,…,n}. Bednarek and Ulam (Generators for Algebras of Relations, 1976) observed that there exists a pair of relations on X that generate all of B_n under the boolean operations and relational composition. In this note we show that B_n can be generated by a single element. In fact, any total order relation on X, either reflexive or strict, generates all of B_n under the boolean operations and relational composition.