Blockchain Papers

Gilles Brassard, Claude Crépeau, Moti Yung

No abstract is available for this record.

Uriel Feige, Amos Fiat, Adi Shamir

No abstract is available for this record.

Gustavus J. Simmons

No abstract is available for this record.

David Chaum, Ivan Damgård, Jeroen van de Graaf

No abstract is available for this record.

Joseph Y. Halpern, Yjoram Moses, Mark R. Tuttle

While the intuition underlying a zero knowledge proof system [GMR85] is that no “knowledge” is leaked by the prover to the verifier, researchers are just beginning to analyze such proof systems in terms of formal notions of knowledge. In this paper, we show how interactive proof systems motivate a new notion of practical knowledge, and we capture the definition of an interactive proof system in terms of practical knowledge. Using this notion of knowledge, we formally capture and prove the intuition that the prover does not leak any knowledge of any fact (other than the fact being proven) during a zero knowledge proof. We extend this result to show that the prover does not leak any knowledge of how to compute any information (such as the factorization of a number) during a zero knowledge proof. Finally, we define the notion of a weak interactive proof in which the prover is limited to probabilistic, polynomial-time computations, and we prove analogous security results for such proof systems. We show that, in a precise sense, any nontrivial weak interactive proof must be a proof about the prover's knowledge, and show that, under natural conditions, the notions of interactive proofs of knowledge defined in [TW87] and [FFS87] are instances of weak interactive proofs.

Gustavus J. Simmons, George Purdy

No abstract is available for this record.

Manuel Blum, Paul Feldman, Silvio Micali

We show that interaction in any zero-knowledge proof can be replaced by sharing a common, short, random string. We use this result to construct the first public-key cryptosystem secure against chosen ciphertext attack.

Hiroyuki Yoshida

1. A. Weil [3] constructed a universal distribution t on the Weil group.The values of I at various test functions give the contributions from the zeros of L-functions which appear in the .explicitformulas.In this note, we shall construct a universal distribution zi on GL(n) and prove the explicit formula for automorphic L-functions using z/ when n-2.For n 2, to derive such a result, we must assume certain property of characters of infinite dimensional representations of GL(n) over a local field.This property, formulated as Conjecture, seems to lie slightly beyond our present knowledge of harmonic analysis.The distributions A have striking formal resemblance to Weil's one.Furthermore they are related to each other so that zl is the "direct image" of z/ for m n.This is a pleasant fact since we think that a discovery of new functorial properties related to zeros of zeta functions would be crucial for the proof of the Riemann hypothesis.

Lance Fortnow

A Perfect Zero-Knowledge interactive proof system convinces a verifier that a string is in a language without revealing any additional knowledge in an information-theoretic sense. We show that for any language that has a perfect zero-knowledge proof system, its complement has a short interactive protocol. This result implies that there are not any perfect zero-knowledge protocols for NP-complete languages unless the polynomial time hierarchy collapses. This paper demonstrates that knowledge complexity can be used to show that a language is easy to prove.

Stewart C. Myers

Stewart C. Myers President of American Finance Association 1983 This paper's title is intended to remind you of Fischer Black's well-known note on “The Dividend Puzzle,” which he closed by saying, “What should the corporation do about dividend policy? We don't know.” 6 I will start by asking, “How do firms choose their capital structures?” Again, the answer is, “We don't know.” The capital structure puzzle is tougher than the dividend one. We know quite a bit about dividend policy. John Lintner's model of how firms set dividends 20 dates back to 1956, and it still seems to work. We know stock prices respond to unanticipated dividend changes, so it is clear that dividends have information content—this observation dates back at least to Miller and Modigliani (MM) in 1961 28. We do not know whether high dividend yield increases the expected rate of return demanded by investors, as adding taxes to the MM proof of dividend irrelevance suggests, but financial economists are at least hammering away at this issue. By contrast, we know very little about capital structure. We do not know how firms choose the debt, equity or hybrid securities they issue. We have only recently discovered that capital structure changes convey information to investors. There has been little if any research testing whether the relationship between financial leverage and investors' required return is as the pure MM theory predicts. In general, we have inadequate understanding of corporate financing behavior, and of how that behavior affects security returns. I do not want to sound too pessimistic or discouraged. We have accumulated many helpful insights into capital structure choice, starting with the most important one, MM's No Magic in Leverage Theorem (Proposition I) 31. We have thought long and hard about what these insights imply for optimal capital structure. Many of us have translated these theories, or stories, of optimal capital structure into more or less definite advice to managers. But our theories don't seem to explain actual financing behavior, and it seems presumptuous to advise firms on optimal capital structure when we are so far from explaining actual decisions. I have done more than my share of writing on optimal capital structure, so I take this opportunity to make amends, and to try to push research in some new directions. A static tradeoff framework, in which the firm is viewed as setting a target debt-to-value ratio and gradually moving towards it, in much the same way that a firm adjusts dividends to move towards a target payout ratio. An old-fashioned pecking order framework, in which the firm prefers internal to external financing, and debt to equity if it issues securities. In the pure pecking order theory, the firm has no well-defined target debt-to-value ratio. Recent theoretical work has breathed new life into the pecking order framework. I will argue that this theory performs at least as well as the static tradeoff theory in explaining what we know about actual financing choices and their average impacts on stock prices. I have arbitrarily, and probably unfairly, excluded “managerial” theories which might explain firms' capital structure choices.1 I have chosen not to consider models which cut the umbilical cord that ties managers' acts to stockholders' interests. I am also sidestepping Miller's idea of “neutral mutation.”2 He suggests that firms fall into some financing patterns or habits which have no material effect on firm value. The habits may make managers feel better, and since they do no harm, no one cares to stop or change them. Thus someone who identifies these habits and uses them to predict financing behavior would not be explaining anything important. The neutral mutations idea is important as a warning. Given time and imagination, economists can usually invent some model that assigns apparent economic rationality to any random event. But taking neutral mutation as a strict null hypothesis makes the game of research too tough to play. If an economist identifies costs of various financing strategies, obtains independent evidence that the costs are really there, and then builds a model based on these costs which explains firms' financing behavior, then some progress has been made, even if it proves difficult to demonstrate that, say, a type A financing strategy gives higher firm value than a type B. (In fact, we would never see type B if all firms follow value-maximizing strategies.) There is another reason for not immediately embracing neutral mutations: we know investors are interested in the firm's financing choices, because stock prices change when the choices are announced. The change might be explained as an “information effect” having nothing to do with financing per se—but again, it is a bit too easy to wait until the results of an event study are in, and then to think of an information story to explain them. On the other hand, if one starts by assuming that managers have special information, builds a model of how that information changes financing choices, and predicts which choices will be interpreted by investors as good or bad news, then some progress has been made. So this paper is designed as a one-on-one competition of the static tradeoff and pecking-order stories. If neither story explains actual behavior, the neutral mutations story will be there faithfully waiting. A firm's optimal debt ratio is usually viewed as determined by a tradeoff of the costs and benefits of borrowing, holding the firm's assets and investment plans constant. The firm is portrayed as balancing the value of interest tax shields against various costs of bankruptcy or financial embarassment. Of course, there is controversy about how valuable the tax shields are, and which, if any, of the costs of financial embarassment are material, but these disagreements give only variations on a theme. The firm is supposed to substitute debt for equity, or equity for debt, until the value of the firm is maximized. Thus the debt-equity tradeoff is as illustrated in Fig. 1. Costs of adjustment. If there were no costs of adjustment, and the static tradeoff theory is correct, then each firm's observed debt-to-value ratio should be its optimal ratio. However, there must be costs, and therefore lags, in adjusting to the optimum. Firms can not immediately offset the random events that bump them away from the optimum, so there should be some cross-sectional dispersion of actual debt ratios across a sample of firms having the same target ratio. The static-tradeoff theory of capital structure. Large adjustment costs could possibly explain the observed wide variation in actual debt ratios, since firms would be forced into long excursions away from their optimal ratios. But there is nothing in the usual static tradeoff stories suggesting that adjustment costs are a first-order concern—in fact, they are rarely mentioned. Invoking them without modelling them is a cop-out. Any cross-sectional test of financing behavior should specify whether firms' debt ratios differ because they have different optimal ratios or because their actual ratios diverge from optimal ones. It is easy to get the two cases mixed up. For example, think of the early cross-sectional studies which attempted to test MM's Proposition I. These studies tried to find out whether differences in leverage affected the market value of the firm (or the market capitalization rate for its operating income). With hindsight, we can quickly see the problem: if adjustment costs are small, and each firm in the sample is at, or close to its optimum, then the in-sample dispersion of debt ratios must reflect differences in risk or in other variables affecting optimal capital structure. But then MM's Proposition I cannot be tested unless the effects of risk and other variables on firm value can be adjusted for. By now we have learned from experience how hard it is to hold “other things constant” in cross-sectional regressions. Of course, one way to make sense of these tests is to assume that adjustment costs are small, but managers don't know, or don't care, what the optimal debt ratio is, and thus do not stay close to it. The researcher then assumes some (usually unspecified) “managerial” theory of capital structure choice. This may be a convenient assumption for a cross-sectional test of MM's Proposition I, but not very helpful if the object is to understand financing behavior.3 But suppose we don't take this “managerial” fork. Then if adjustment costs are small, and firms stay near their target debt ratios, I find it hard to understand the observed diversity of capital structures across firms that seem similar in a static tradeoff framework. If adjustment costs are large, so that some firms take extended excursions away from their targets, then we ought to give less attention to refining our static tradeoff stories and relatively more to understanding what the adjustment costs are, why they are so important, and how rational managers would respond to them. But I am getting ahead of my story. On to debt and taxes. Debt and taxes. Miller's famous “Debt and Taxes” paper 27 cut us loose from the extreme implications of the original MM theory, which made interest tax shields so valuable that we could not explain why all firms were not awash in debt. Miller described an equilibrium of aggregate supply and demand for corporate debt, in which personal income taxes paid by the marginal investor in corporate debt just offset the corporate tax saving. However, since the equilibrium only determines aggregates, debt policy should not matter for any single taxpaying firm. Thus Miller's model allows us to explain the dispersion of actual debt policies without having to introduce non-value-maximizing managers.4 Trouble is, this explanation works only if we assume that all firms face approximately the same marginal tax rate, and that is an assumption we can immediately reject. The extensive trading of depreciation tax shields and investment tax credits, through financial leases and other devices, proves that plenty of firms face low marginal rates.5 Given significant differences in effective marginal tax rates, and given that the static tradeoff theory works, we would expect to find a strong tax effect in any cross-sectional test, regardless of whose theory of debt and taxes you believe. Figure 2 plots the net tax gain from corporate borrowing against the expected realizable tax shield from a future deduction of one dollar of interest paid. For some firms this number is 46 cents, or close to it. At the other extreme, there are firms with large unused loss carryforwards which pay no immediate taxes. An extra dollar of interest paid by these firms would create only a potential future deduction, usable when and if the firm earns enough to work off prior carryforwards. The expected realizable tax shield is positive but small. Also, there are firms paying taxes today which cannot be sure they will do so in the future. Such a firm values expected future interest tax shields at somewhere between zero and the full statutory rate. In the “corrected” MM theory 28 any tax-paying corporation gains by borrowing; the greater the marginal tax rate, the greater the gain. This gives the top line in the figure. In Miller's theory, the personal income taxes on interest payments would exactly offset the corporate interest tax shield, provided that the firm pays the full statutory tax rate. However, any firm paying a lower rate would see a net loss to corporate borrowing and a net gain to lending. This gives the bottom line. There are also compromise theories, advanced by D'Angelo and Masulis 12, Modigliani 30 and others, indicated by the middle dashed line in the figure. The compromise theories are appealing because they seem less extreme than either the MM or Miller theories. But regardless of which theory holds, the slope of the line is always positive. The difference between (1) the tax advantage of borrowing to firms facing the full statutory rate, and (2) the tax advantage of lending (or at least not borrowing) to firms with large tax loss carryforwards, is exactly the same as in the “extreme” theories. Thus, although the theories tell different stories about aggregate supply and demand of corporate debt, they make essentially the same predictions about which firms borrow more or less than average. The net tax gain to corporate borrowing. So the tax side of the static tradeoff theory predicts that IBM should borrow more than Bethlehem Steel, other things equal, and that General Motors' debt-to-value ratio should be more than Chrysler's. Costs of financial distress. Costs of financial distress include the legal and administrative costs of bankruptcy, as well as the subtler agency, moral hazard, monitoring and contracting costs which can erode firm value even if formal default is avoided. We know these costs exist, although we may debate their magnitude. For example, there is no satisfactory explanation of debt covenants unless agency costs and moral hazard problems are recognized. The literature on costs of financial distress supports two qualitative statements about financing behavior.6 Risky firms ought to borrow less, other things equal. Here “risk” would be defined as the variance rate of the market value of the firm's assets. The higher the variance rate, the greater the probability of default on any given package of debt claims. Since costs of financial distress are caused by threatened or actual default, safe firms ought to be able to borrow more before expected costs of financial distress offset the tax advantages of borrowing. Firms holding tangible assets-in-place having active second-hand markets will borrow less than firms holding specialized, intangible assets or valuable growth opportunities. The expected cost of financial distress depends not just on the probability of trouble, but the value lost if trouble comes. Specialized, intangible assets or growth opportunities are more likely to lose value in financial distress. Firms prefer internal finance. They adapt their target dividend payout ratios to their investment opportunities, although dividends are sticky and target payout ratios are only gradually adjusted to shifts in the extent of valuable investment opportunities. Sticky dividend policies, plus unpredictable fluctuations in profitability and investment opportunities, mean that internally-generated cash flow may be more or less than investment outlays. If it is less, the firm first draws down its cash balance or marketable securities portfolio.7 If external finance is required, firms issue the safest security first. That is, they start with debt, then possibly hybrid securities such as convertible bonds, then perhaps equity as a last resort. In this story, there is no well-defined target debt-equity mix, because there are two kinds of equity, internal and external, one at the top of the pecking order and one at the bottom. Each firm's observed debt ratio reflects its cumulative requirements for external finance. The pecking order literature. The pecking order hypothesis is hardly new.8 For example, it comes through loud and clear in Donaldson's 1961 study of the financing practices of a sample of large corporations. He observed 13 that “Management strongly favored internal generation as a source of new funds even to the exclusion of external funds except for occasional unavoidable ‘bulges’ in the need for funds.” These bulges were not generally met by cutting dividends: Reducing the “customary cash dividend payment… was unthinkable to most managements except as a defensive measure in a period of extreme financial distress” (p. 70). Given that external finance was needed, managers rarely thought of issuing stock: Though few companies would go so far as to rule out a sale of common under any circumstances, the large majority had not had such a sale in the past 20 years and did not anticipate one in the foreseeable future. This was particularly remarkable in view of the very high Price-Earnings ratios of recent years. Several financial officers showed that they were well aware that this had been a good time to sell common, but the reluctance still persisted. (pp. 57–58). Of course, the pecking order hypothesis can be quickly rejected if we require it to explain everything. There are plenty of examples of firms issuing stock when they could issue investment-grade debt. But when one looks at aggregates, the heavy reliance on internal finance and debt is clear. For all non-financial corporations over the decade 1973–1982, internally generated cash covered, on average, 62 percent of capital expenditures, including investment in inventory and other current assets. The bulk of required external financing came from borrowing. Net new stock issues were never more than 6 percent of external financing.9 Anyone innocent of modern finance who looked at these statistics would find the pecking order idea entirely plausible, at least as a description of typical behavior. Writers on “managerial capitalism” have interpreted firms' reliance on internal finance as a byproduct of the separation of ownership and control: professional managers avoid relying on external finance because it would subject them to the discipline of the capital market.10 Donaldson's 1969 book was not primarily about managerial capitalism, but he nevertheless observed that the financing decisions of the firms he studied were not directed towards and that to explain decisions would have to start by the “managerial of corporate finance. This is given the of finance theory in the it is not so that financing by a pecking order against interests. financing with I to the pecking order story because I could think of no theoretical for it that would in with the theory of modern finance. An could be made for internal financing to avoid issue costs, and if external finance is needed, for debt to avoid the still higher costs of But issue costs in do not seem large enough to the costs and benefits of leverage in the static tradeoff story. However, recent work based on information gives predictions in line with the pecking order The is based on a paper by and although I will down that paper's to the firm has to in order to some valuable investment be this net value and be what the firm will be if the opportunity is The firm's what and are, but investors in capital markets do they see only a of values The information is as from the information capital markets are and MM's Proposition I in the sense that the stock of debt to assets is if information to investors is constant. The to by a security issue is the of the firm's investment There is also a the firm may have to sell the securities for less than they are really the firm issues stock with an aggregate market when of will consider debt issues in a However, the the are really That is, is what the new will be other things equal, when investors the special and I managers might in this The one we think makes the most sense is the or value of the firm's That is, the about the value of the in the firm. investors know the will do In the investors who any stock issue will assume that the is not on their and will the they are to If the information is is and the firm will always even if the only good for the funds is to them in the If the information is the firm may a investment opportunity than issue Thus, given and and given that stock is the greater the per the less value is given to new and the less The cost of relying on external We usually think of the cost of external finance as administrative and costs, and in some cases of the new securities. information the of a different of the that the firm will choose not to and will therefore a This cost is if the firm can enough internally-generated cash to its opportunities. The advantages of debt over equity If the firm external it is off issuing debt than equity securities. The rule is, safe securities before This is explaining that the firm issues and if the of its investment is greater than or to the by which the new are if or if For example, suppose the investment but in order to that the firm must issue that are really It will go ahead only if is at least If it is only the firm to the for the value of the firm is by but the are The could have this by the firm's cash that is The only he can do now is to the security issue to For example, if could be cut to the investment could be without the value of The way to is to issue the safest securities whose future value changes least when the information is to the Of course, is so it is loose to of the it. However, there are cases in which the value of is always less for debt than for For example, if the firm can issue debt, is and the firm never a valuable investment Thus, the to issue debt is as good as cash in the if default risk is the value of will be less for debt than for equity if we make the of Thus, if the has information it is to issue debt than This assumes that new or debt would be if the managers' information is so that any security issue would be In this the firm want to make as large as to take advantage of new If stock would seem than debt The rule seems to debt when investors the and equity, or some other when they The trouble with this strategy is you in investors' If you know the firm will issue equity only when it is and debt you will to equity unless the firm has its is, unless the firm has so much debt that it would face costs in issuing Thus investors would the firm to follow a pecking this is too The model just would need of out before it could actual behavior. I have it just to how models based on information can predict the two of the pecking order the for internal the for debt over equity if external financing is I will now what we know about financing behavior and try to make sense of this in of the two I with about financing behavior, and then a few from evidence or personal Of even based on good statistics have been to away under so with external investment are by debt issues and internally-generated stock issues a relatively as has this is what many managers they are to This is what the pecking order hypothesis in the first However, it might also be explained in a static tradeoff theory by adding significant costs of equity issues and the tax of capital gains to This would make external equity relatively It would explain why companies target dividend low enough to avoid having to make stock It would also explain why a firm whose debt ratio target not immediately issue back debt, and a more debt-to-value ratio. Thus firms might take extended excursions their debt that the static tradeoff hypothesis as usually rarely this of adjustment But the costs of seems small. It is thus hard to explain extended excursions a firm's debt target by an static tradeoff firm could quickly issue debt and back if personal income taxes are important in explaining firms' apparent for internal equity, then difficult to explain why external equity is not strongly is, why most firms gradually to lower target payout ratios and the cash to of security Firms try to stock issues when security prices are Given that they external they are more likely to issue stock than stock prices have than they have For example, past stock were one of the variables in study of firms' choices between new debt and new equity and have similar behavior in the This is to static tradeoff If firm value the debt-to-value ratio and firms ought to issue debt, not equity, to their capital The is to the pecking order There is no reason to that the information is more when stock prices are if there were such a investors would have learned it by and would the firm's issue There is no way firms can take advantage of of new equity in a rational against and growth opportunities. Firms holding valuable intangible assets or growth opportunities to borrow less than firms holding tangible assets. For example, and a significant relationship between of investment in and research and and the of borrowing. They also a significant positive relationship between the rate of capital and and the of borrowing. the same by a different for a firm's and growth opportunities was the difference between the market value of its debt and equity securities and the cost of its tangible assets. The higher this he the less the firm's debt-to-value ratio. There is plenty of evidence that the of borrowing is determined not just by the value and risk of the firm's but also by the type of assets it For example, without this the static tradeoff theory would specify all target debt ratios in of not book Since many firms have market values far in of book values if book values are in current we ought to see at least a few such firms operating at very high book debt of we do This to make as as we that book values reflect assets-in-place assets and values reflect and growth opportunities as well as Thus, firms do not set target book debt ratios because the values are for the values of assets in Masulis has that stock prices on average, when a firm

B.W. Wetherilt

This thesis is an attempt to generalise to the odd orthogonal group Γ_K, over an Infinite field K not of characteristic two, the work of Schur [S], and more recently Green [G], on the general linear group G_K using the approach of Weyl [W] in characteristic zero. The special feature here is that we treat Γ_K as merely a group of matrices defined by the vanishing of polynomials in its coefficients (the classical view) rather than a group generated by elements derived from an associated Lie algebra, the approach used initially by Chevalley and adopted by most authors in recent times.
\n
\nAfter generalising Green's [G] Schur algebra for G_K to Γ_K in §0 we prove in §1 Chevalley's famous theorem on the 'Big Cell' in G_K and then, by an easy extension, prove it for the Big Cell in Γ_K. Chevalley's original proof uses representations of Lie algebras, ours requires nothing but a little knowledge of the coordinate ring K_+[G] of all 'polynomial' functions on G_K . We define K[Γ], the coordinate ring of Γ_K, to be the space of all polynomial functions on G_K restricted to Γ_K and in §2 give a generating set of the kernel of the restriction map ψ_K:K_+ [G]→K[Γ]. This generalises Weyl's result in characteristic zero. In §3 we use this result to show that the family, or 'scheme', of rings K[Γ] (K varying over all infinite fields not of characteristic two) is 'defined over Z' ; in fact K[Γ] is naturally isomorphic to K θ Z[Γ_Q], where Z[Γ_Q] is the subring of Q[Γ] spanned by 'monomial' functions. This enables us to formulate a 'modular' representation theory for Γ which connects polynomial representations of Γ_Q with those of Γ_K.
\n
\nIn §4 we investigate the Schur algebras of Γ_Q following Weyl [W] and in §5 find a complete set of irreducibles for each of them, once again following the lead of Weyl. In §6 we attempt to 'reduce' these modules modulo p to obtain 'Weyl' modules for Γ_K, a task only partially completed.

Ruy de Queiroz, Luiz Carlos Pereira, Edward Hermann Hæusler

This volume contains the Proceedings of the 10th Workshop on Logic, Language, Information and Computation (WoLLIC'2003). The Workshop was held in Ouro Preto, Minas Gerais, Brazil from July 29 to August 1, 2003, in the Escola de Minas of the Universidade Federal de Ouro Preto ( UFOP ). WoLLIC is a series of workshops which started in 1994 with the aim of fostering interdisciplinary research in pure and applied logic . The idea is to provide a forum which is large enough in the number of possible interactions between logic and the sciences related to information and computation, and yet is small enough to allow for concrete and useful interaction among participants. Previous versions were held at: Recife (Pernambuco, Brazil) in 1994 and 1995; Salvador (Bahia, Brazil) in 1996; Fortaleza (Ceará, Brazil) in 1997; São Paulo (Brazil) in 1998; Itatiaia (Rio de Janeiro, Brazil) in 1999; Natal (Rio Grande do Norte) in 2000; Brasília (Distrito Federal, Brazil) in 2001; Rio de Janeiro (Brazil) in 2002. Scientific sponsorship comes from the Interest Group in Pure and Applied Logics ( IGPL ), the European Association for Logic, Language and Information ( FoLLI ), the Association for Symbolic Logic ( ASL ), European Association for Theoretical Computer Science ( EATCS ), the Sociedade Brasileira de Computação ( SBC ), and the Sociedade Brasileira de Lógica ( SBL ). Funding was kindly given by:(i) CNPq ( Conselho Nacional de Desenvolvimento Científico e Tecnológico , the scientific and technological development council of the Brazilian Ministério da Ciência e Tecnologia ) (grant 450709/2003-5);(ii) CAPES ( Fundação Coordenação de Apoio ao Aperfeiçoamento de Pessoal de Nível Superior , a Foundation for the Development of Higher-Education under the Brazilian Ministério da Educação e do Desporto ) (grant PAEP0565/03);(iii) FAPEMIG ( Fundação de Amparo à Pesquisa do Estado de Minas Gerais , the Minas Gerais state foundation for the support of scientific research);(iv) Escola de Minas da UFOP ( Universidade Federal de Ouro Preto ). Contributions were received in the form of short papers in all areas related to logic, language, information and computation, including:pure logical systems, proof theory, model theory, algebraic logic, type theory, category theory, constructive mathematics, lambda and combinatorial calculi, program logic and program semantics, logics and models of concurrency, logic and complexity theory, proof complexity, foundations of cryptography (zero-knowledge proofs), descriptive complexity, nonclassical logics, nonmonotonic logic, logic and language, discourse representation, logic and artificial intelligence, automated deduction, foundations of logic programming, logic and computation, and logic engineering. Apart from the contributed papers (15), and the invited talks (5), the programme includes 5 tutorial lectures: 1. Algorithmic Randomness and Derandomization by Eric Allender (Department of Computer Science, Rutgers, the State University of New Jersey, USA) 2. Generalized Quantifiers by Lauri Hella (Department of Mathematics, Statistics and Philosophy, University of Tampere, Finland) 3. Implicit computational complexity by Jean-Baptiste Joinet (Preuves-Programmes-Systèmes, Université Paris 7, France) 4. Proof search foundations for logic programming by Dale Miller (INRIA/Futurs/Saclay, and Laboratoire d'Informatique, École Polytechnique, France) 5. Iterated theory change by Hans Rott (Institut für Philosophie, Universität Regensburg, Germany) All papers in the volume were reviewed by the program committee consisting of Mauricio Ayala-Rinóon ( Departamento de Matemática, Universidade de Brasília, Brazil ) Argimiro Arratia ( Depto. Matematicas, Universidad Simon Bolivar, Venezuela ) Alessandra Carbone ( Institut des Hautes Études Scientifiques, and Université de Paris XII, France ) Marcelo Coniglio ( Centro de Lógica e Epistemologia, Universidade Estadual de Campinas, Brazil ) Gilles Dowek ( INRIA, France ) Arnaud Fleury ( Facoltà di Scienze, Università di Verona, Italy ) Dexter Kozen ( Cornell University, USA ) Maarten Marx ( ILLC, Faculty of Science, Universiteit Amsterdam, The Netherlands ) Anto˚nio Carlos da Rocha Costa ( Escola de Informática, Universidade Católica de Pelotas, Brazil ) Dieter Spreen ( Fachbereich Mathematik, Theoretische Informatik, Universität Siegen, Germany ) Luiz Carlos Pereira ( Departamento de Filosofia, PUC-Rio and UFRJ, Brazil ) Jouko Väänänen ( Department of Mathematics, University of Helsinki, Finland ) Renata Wassermann ( Departamento de Cie˚ncia da Computação, Instituto de Matemática e Estatística, Universidade de São Paulo, Brazil ) The organising committee consisted of Lucília Figueiredo ( Departamento de Computação, Universidade Federal de Ouro Preto, Brazil ) Fred Ulisses Maranhão ( Centro de Informática, Universidade Federal de Pernambuco, Brazil ) Anjolina Grisi de Oliveira ( Center of Informatics, Universidade Federal de Pernambuco, Brazil ) Elaine Pimentel ( Departamento de Matemática, Universidade Federal de Minas Gerais, Brazil ) (Co-Chair) Ruy de Queiroz ( Center of Informatics, Universidade Federal de Pernambuco, Brazil ) (Co-Chair) Maria Angela Weiss ( Departamento de Matemática, Universidade de São Paulo, Brazil ) The volume will be published as volume 84 in the series Electronic Notes in Theoretical Computer Science ( ENTCS ). This series is published electronically through the facilities of Elsevier B.V. and its auspices. The volumes in the ENTCS series can be accessed at the URL http://www.elsevier.nl/locate/entcs A printed version of the current volume has been distributed to the participants at the workshop in Ouro Preto. We are very grateful to the following persons, whose help has been crucial for the success of WoLLIC'2003: Mike Mislove, one of the Managing Editors of the ENTCS series, for his assistance with the use of the ENTCS style files; Thanks are also due to the Department of Mathematics of Universidade Federal de Minas Gerais and the Department of Computing of the Universidade Federal de Ouro Preto, which has provided the logistic support to the organising committee. August 2, 2003 Ruy de Queiroz, Elaine Pimentel, Lucilia Figueiredo

David W. Pratt

Zero-field and high-field optical detection of magnetic resonance (ODMR), electron paramagnetic resonance (EPR), and optical spectroscopy experiments have been performed on several systems in order to further basic knowledge of the structure, reactions, and response to radiation of atoms, molecules, and ions in their ground and/or excited electronic states. Particularly noteworthy results for the present contract year include the determination of the complete magnetic and optical properties of the lowest triplet states of 1-chloro, 1-bromo, and 1-iodonaphthalene, the development of a microscopic model for the intramolecular heavy-atom effect in the /sup 3/(..pi..,..pi..*) states of aromatic molecules, a detailed analysis of the angular dependence of the hyperfine and quadrupole structure in triplet 1-bromonaphthalene, observation of proton hyperfine structure in the hf ODMR spectra of short-lived triplet states, a definitive paper on the relative importance of spin delocalization and second-order spin-orbit coupling effects in /sup 3/(n,..pi..*) benzophenone (a phototype photochemical system), a detailed analysis of the level-anticrossing spectra of several triplet state benzophenones which exhibit hyperfine structure in the cross-relaxation region (thus permitting the determination of key magnetic parameters in the complete absence of perturbing microwave or radiofrequency fields), optical detection of ground-state NQR transitions in host crystal molecules, the observation of strong radiofrequency transitions near avoided crossing points in Zeeman energy level diagrams of photoexcited triplet states, the construction of zero-field ODMR, ODENDOR, and hf ODENDOR spectrometers, measurements of the activation parameters for ring interconversions of several free radicals containing five- and six-membered rings, and experimental proof that the triplet state of trimethylenemethane (a key reactive intermediate in organic chemistry) is the ground state.

K.T. Parker

A review of optimal control theory for linear systems with quadratic cost functions is presented. Some of the theoretical and practical limitations are discussed with special reference to distributed parameter systems. First a procedure is described for finding the optimal control by constructing a sequence of controllers that converges to the optimal; this method is valid for systems of infinite dimension provided that the operators in the state differential equation satisfy certain conditions. The proof is carried out both for the finite and infinite time interval and the connection is shown with the Riccati equation. The main problem in implementation is that one needs complete knowledge of the state at all times in order to build the optimal controller, this is almost certainly impossible for distributed parameter systems. When the state cannot be measured completely it is proved that an optimal control is realisable for time invariant finite dimensional systems.
\n
\nThe problems of finding this control are then investigated and computational methods discussed. If the optimal control with complete knowledge of the state cannot be implemented, a method is presented whereby one can find bounds on the possible increase in the value of the cost function arising from the use of some sub-optimal control; several examples are considered. The constrained optimal control depends on the initial state and new optimisation criteria must be put forward to deal with the case in which the initial state is unknown; the most common consist of minimising the cost that can result from the worst initial state. It is then shown how the controllers designed according to these criteria may be improved by using one's limited observation at time zero to place some constraints on the initial state. The Liapunov matrix equation plays an important part in calculating the cost of any control so reducing the computational effort in its solution is useful. It is shown how this can be done and it is of special relevance for distributed parameter systems with their states expressed as an infinite series of eigenfunctions; the results are applied to a diffusion equation example.
\n
\nFinally, it is shown how optimal control theory may be applied to the design of proportional-integral-derivative controllers. This is done from two standpoints and the resulting controllers are shown to be identical, though the second method of proof is valid for infinite dimensional systems. The results are then applied to a simple example and to a distributed population dynamics system. The practicality of the methods of the thesis are applied to a system with realistic parameters; recommendations are made as to the best approaches.
\n

É. Sanchez-Palencia

No abstract is available for this record.

B. Balamurugan, T. Poongodi, M. R. Manu, S. Karthikeyan · 5 authors

The moving image archive of the US Agency for International Development (USAID) includes a copy of the film The Double Day (1975), cataloged in the series Moving Images Relating to International Development Programs and Activities, 1979–1991, a collection of more than eight hundred titles “created to provide information on assistance programs supported by the Agency for International Development (AID).”1 Yet, The Double Day does not, in fact, directly depict or engage with any specific development or aid initiative. Instead, the film—directed by US-based Brazilian filmmaker Helena Solberg as part of the International Women’s Film Project collective and described as “the first Latin American feminist documentary”—examines the gendered dynamics of paid and unpaid labor through the testimonies of women from Argentina, Bolivia, Venezuela, and Mexico.2 Its presence in the USAID archive is likely a consequence of its funding history, having received support from the Inter-American Foundation, a USAID-affiliated entity; the development agencies of Denmark, Norway, and Sweden; the United Nations Development Program; and US philanthropist Calvin Cafritz.3These transnational funding structures not only enabled the film’s production but also determined its archival destination, which renders legible its place within the history of international development.4 The Double Day’s institutional trajectory reflects the shifting configurations of aid, gender, and media during a historic moment when women were being repositioned at the center of what Arturo Escobar has described as development’s “regimes of visuality.”5 Especially relevant to The Double Day’s production and exhibition was the international institutional framework of Women in Development (WID). Emerging in the early 1970s and culminating in United Nations’ proclamation of 1975 as International Women’s Year, WID emphasized women’s participation in the global economy as both an index and mechanism of development. Indeed, The Double Day premiered at the World Conference of the International Women’s Year, held in Mexico City.6 Within this context, the film forms part of a broader trajectory of media use by international organizations that intensified during the 1970s—as best exemplified by Media Habitat, a collection of 236 documentary films commissioned by the United Nations to represent urban and rural development initiatives for the 1976 Habitat Conference on Human Settlements in Vancouver. As a policy-shaping initiative, Media Habitat primarily featured films from the Global South intended not only to illustrate but also to help codify standardized audiovisual markers of “underdevelopment” that determined access to the emerging global economic order and to international aid.7Framed in relation to these international institutions and their operations, The Double Day could similarly be considered “development media”—exemplifying the type of nonfiction media produced and distributed outside of the commercial film circuits whose aspects and subcategories have been variously described in scholarship as nontheatrical, useful, sponsored, institutional, industrial, educational, or nonprofessional/amateur.8 Scholars working in this area have emphasized the institutional contexts of such media’s production and exhibition infrastructures as shaping its instrumentalized effects. From a feminist perspective, such an approach is crucial to grappling with the broader question of how “gender impacts [these works’] shape, content, and trajectories.”9 Yet we also argue that, taken in isolation, the institutional and infrastructural contexts are insufficient to account for the complex relationship between media and development, potentially not only limiting our understanding of the reach and impact of development but also distorting our interpretive conclusions. For example, to categorize The Double Day as “development media” is to overlook the film’s place within Solberg’s directorial oeuvre, as well as within the histories of both transnational women’s filmmaking and radical Latin American documentary cinema to which it simultaneously belongs. Such exclusive framing is especially limiting given that women globally were disproportionately engaged in nonfiction production throughout the twentieth century—sometimes by political choice but more often due to structural exclusions from fiction filmmaking. Even in nonfiction historiography, however, institutional media has remained particularly marginal, reinforcing hierarchies that separate such works from the aesthetic and authorial frameworks through which film history has been constructed.10 This marginalization not only tends to erase women’s contributions but also presumes a “weak” or derivative authorship, rendering these films unworthy of the interpretive attention needed to apprehend their aesthetic and political complexity.11 The same dynamic is likely to structure assumptions about “development media” as well.Categorizing The Double Day exclusively within this category would further prompt us to assume top-down institutional analyses that have been characteristic of both institutional media methodologies and the scholarship on development at large. This, in turn, would risk obscuring this film’s radical Marxist approach to women’s labor as well as its concrete contribution to activism and its attendant grassroot structures. In Mexico City, The Double Day became a catalyst for feminist solidarity in practice when one of the film’s protagonists, Bolivian activist and trade unionist Domitila Barrios de Chungara, was invited to participate in the Tribune of Non-Governmental Organizations held alongside the official UN conference.12 There, Barrios de Chungara challenged Western feminist priorities by reframing the debate around labor, class, and imperialism, helping to articulate a shared Third World feminist agenda that significantly departed from the developmentalist vision of the United Nations and USAID.13 Seen through the lens of activist media, The Double Day helped forge transnational solidarity networks by enabling information exchange across the diverse voices that shaped its making—from the women featured in the film to the activists who circulated it—revealing a considerably more dynamic interplay between institutional and grassroots or contingent media practices.Moreover, the film’s Latin American context—reflected in Solberg’s formation in Brazil as the only woman in Cinema Novo, its focus on women from across the region, and its premiere and key reception in Mexico City—requires grappling with the regional specificities of the very notion of development in its multiple iterations.14 Far from being an epistemological and political framework imposed solely by the Global North, both the practices of development and the theoretical foundations of developmentalism (understood as a broad and polysemic set of discourses) were shaped through the active participation of Latin American economists.15 Within this iteration, underdevelopment, as a constitutive notion of developmentalism, became central to a distinctly critical strand, which by the late 1960s became known as the dependency theory.16 This same approach is reflected in some of the best-known Latin American radical film manifestos of the time, arising precisely from the same milieus to which Solberg belonged.17These various considerations of the film’s history illustrate the methodological challenges confronting feminist scholars seeking to assess the impact of development on media projects, theories, and practices. To disregard the developmentalist context of such works by emphasizing their political aesthetics and affects risks reproducing a romanticized narrative of heroic resistance (albeit from a feminist perspective). Yet to engage exclusively with their institutional and material infrastructures risks naturalizing developmentalism’s political and epistemological foundations at the expense of the goals and beliefs of the many women who participated in these projects. The contradictions and ambivalences that animate such histories call for feminist frameworks capable of holding both institutional complicity and radical possibility in view.This challenge resonates with ongoing debates about the politics of the archive and what Allyson Field has termed “the practice of informed speculation.”18 As she reminds us, feminist, queer, and decolonial methodologies have long taught us to “press at the limits” of the archive to “inoculate our scholarship against our evidence’s afflictions.”19 The concern that the evidence we draw on in our analysis reproduces the very structures and blind spots of the dominant ideology and therefore shapes and delimits our interpretation becomes particularly urgent when engaging the developmentalist media corpus. Informed speculation offers an alternative by inviting the experimental, creative, and speculative rewriting of history, mobilizing the archive “in a project that runs counter to the original purpose, or the imperative to preserve, or the conditions that led to erasure.”20 Yet, as Field cautions, such speculative gestures must remain grounded in a deep and “intimate familiarity with the archive” that we are working with and against. Building on this imperative, we suggest that the developmentalist archive, in particular, demands expansion and critical reconsideration in ways that unsettle the very disciplinary frameworks through which it has been studied as well as the larger institutional contexts for such knowledge production.Our focus on The Double Day in the opening of this introduction thus foregrounds the entanglements of institutional and grassroots forces, local and international contexts, structural and interpersonal relations, and creative and economic factors that have shaped not only this film but the broader ecosystem of development media projects—and their preservation—over time. Addressing such a constellation involves transgressing methodologically entrenched divisions between political economy and aesthetics, between material infrastructures and affective regimes; reckoning with divergent periodizations across film history and world economics; and situating these within the local specificities of women’s movements and international institutional programs. It also demands attentiveness to the coexistence of multiple, and sometimes competing, understandings of development—each historically, geographically, and ideologically situated.We imagine this special issue as an opening toward a critical dialogue, not only about how such an approach might be enacted in practice but also about the far-reaching ways development paradigms have shaped both our objects of study and the contours of the field itself. The decision to center institutionally sponsored films across all the essays in this issue is deliberate and enables us to highlight institutional critique as a vital methodological imperative within our analytical framework. Created within the frameworks of international organizations, state agencies, or NGOs, these films’ histories make legible the institutional logics that underwrite their production. Yet our critique does not stop at these specific entities. Rather, we argue for a broader interrogation of the political conditions and institutional infrastructures that shape media and knowledge production more generally. This includes contemporary corporations embedded in the digital platform economy, from streaming services to the rapid expansion of AI. Equally critical is a reflexive examination of academia itself, where departments of economics, political science, and centers for development have played a formative role in producing and legitimizing developmentalist theories and policy frameworks. While the humanities and arts have at times offered critical alternatives, they have also frequently mirrored and reinforced many of the same developmentalist assumptions. A feminist analysis of the nexus between development and media must therefore unsettle not only dominant archives but also the institutional and disciplinary foundations of our own scholarly practices.As scholars, we share the complex position of navigating the same tensions between institutional complicity and emancipatory aspiration as many of the media-makers whose work we study. Mirroring our subjects is also the transnational, collective mode of this special issue’s own production as it emerges from an ongoing informal working group we have sustained over several years. While relying on institutional and disciplinary affordances—such as university funding for conferences or access to academic publishing platforms—we have been working toward creating a community that exceeds, and often resists, the prevailing logics of our academic institutions. Our aim has been to create a space for shared inquiry and mutual support that pushes back against disciplinary siloing and technocratic neoliberal assessment modes of both labor and knowledge production—and this certainly extends to our experience collaborating with the journal editors throughout the publication process. Our goal has been to examine both the persistence and variability of developmentalism, understood as what Gustavo Esteva calls a “powerful but fragile semantic constellation,” as a conceptual formation that has historically inspired, legitimized, and mobilized media projects across Asia, Africa, and Latin America.21 And gendered biopolitics, from population control to gender mainstreaming, have remained integral to development policies and media practices, recurring across formats from institutional newsreels to film festivals.We share the conviction that, far beyond the history of nonfiction institutional media, development (as both a broad ideological project and a network of material and institutional practices) and developmentalism (as a set of discourses and theoretical models associated with development) have exerted a far-reaching influence on film and media cultures at large. As such, they must be treated as a major force in shaping global film and media systems and also the many ongoing assumptions behind their critical discourses. The discipline of communication studies was founded on modernization theory governed by Cold War goals of dissemination of Western liberal democracy around the world, while “an area studies framework allowed compartmentalizing Western and non-Western outcomes of technologies that were always claimed to be universal.”22 Despite critique from postcolonial and critical race studies, many of these frameworks have remained foundational for media theory.23 In historical scholarship, as we increasingly move beyond “modernity” as a dominant conceptual anchor, engaging with practices and discourses of development opens more precise analytical pathways. These film and media’s entanglements with the logics of and economic and the associated with as well as their conceptual underdevelopment, and impact in as diverse as and of media aesthetic and paradigms in film and film and funding are developmentalist assumptions to the they to underwrite the narrative and logics of and global media from the structure of the film to the cultures of argue that a examination of the historical entanglements between film and developmentalist aesthetics, modes of as well as infrastructures and critical the and that our contemporary media is a of the historical contours of development as a field of inquiry embedded within a of some of the methodologies by the featured in this special a of this complex history, to the larger at in media, development, and gender all its development a it as an of be with practices as divergent as and in In as we work on this the of the of the USAID the ideological that have the history of international the and of this on the global its a from development as a global practice and as an institutional and which over the has as a with its own media Yet or does not erase the historical impact of these the contradictions they have reflected and over the as the of development several crucial to the economic theories of development initiatives to and through the of the development an international policy framework at from the Global to the of the Global the by the political role of and the of the International the on was challenged by dependency theory and at development as global structural the neoliberal of the the Programs by the and World imposed and as conditions for and forms of assistance became known as the major markers for international development development has moving beyond economic to such as the Human Development and the Development and from international organizations such as the United Nations to a broader network of These frameworks increasingly of and liberal of and with what in many ways to various while the of the to development’s epistemological more scholarship has toward a of its and material the field has to a of and critical by and scholars, which development as a dynamic of conceptual and political to these the studies in this special issue call for sustained analysis in place of In we draw from a of and that in of of gender and to this special issue engage that and from Mexico to contemporary specific local historical of global distinctly feminist methodologies as well as attention to studies that this issue a in the global history of development on and documentary work in Mexico how early women infrastructures as of while US films an early of state and transnational on a outside the Global as the of developmentalist both the and markers of development media, its to the and Latin central grounded in archival also women’s in transnational and the methodological of archives on study of the series to a a digital media not by but by women not as but as subjects and within circuits of neoliberal and the aesthetics and of how development’s has models of to contemporary neoliberal paradigms of and analysis how digital and gender and practices, discourses on and their of these essays the of some of the historical of developmentalist as the question of the role of the state within such on a notion of economic as a and the dominant of development that the state as the for and through infrastructural projects. This understanding of development was shared across both of the as well as in the Third The United and the increasingly mobilized international in the of the modes of international at the postcolonial of policy and ideological These programs were at the expansion of their and of while with the and decolonial of The conceptual between modernization and development that the Cold in of and hierarchies of that long and As an of postcolonial their role as of international aid concern about the of Western development projects. In alternative across the Global South that to structural between and through policies of and In many they were further the global structures. In Latin for example, this approach was through organizations such as the United Nations for Latin and the both developmentalist projects and their have taken many forms historically, and they have and they have been to a of projects, and postcolonial and development has been and in ways and with frequently political While many of these alternative frameworks the embedded in dominant Western they often technocratic and assumptions. gender and gender as for the of to be shaped by This becomes particularly in the media that of development where women frequently a crucial associated with and women were as both the subjects and of their participation in the and labor often as the index of In this study of from the 1970s how women were as of this as these about women’s urban and recurring and of a within the own of and critique that official examination of archives and enables a feminist interrogation of their mobilizing a of the in the of contribution to this issue similarly the of a dynamic within as well as across ideological the of women’s and the media of the and as active in labor and as integral to the technocratic women became of as their labor remained a of and analysis and archival with attention to the specific of and It also transnational that as a and affective a nexus of and practices through which gender, media, and developmentalism one film not as a but as part of the of alongside and work a broader concern of this special media as a of developmentalist projects. The debates the World and which international such as the United Nations and a critical historical for such primarily by postcolonial and of the for the of media and communication infrastructures in as to counter Western The a between and economic how systems of media and reinforced global hierarchies of and in an agenda that supported and alternative media infrastructures across postcolonial contexts, the framework gender as an analytical This “gender in the 1970s by of the Women in Development in relation to The Double its political critique of with its broader to center women in development policy through and This was also in of media, which was shaped by its international reach and audiovisual production and and and Yet, as WID institutional it also to the and of the women’s development programs often by in These were by a of studies, and on and the to of women’s presence and through the of their economic and In this on the filmmaker this history directly by the and of for women by the WID framework during the with and agencies the of and against Women in at the of the neoliberal turn, when institutional media often the only to access and support to projects. The an by this dynamic as of the from the Global South are to engage with the developmentalist assumptions funding models that their similarly the as a in developmentalist media history by the of and centers on the Film a between of and the attention toward the and labor by and work was foundational the of and the of audiovisual aid, as both a of development projects and a critical for their the in this issue argue for a with media, gender, and developmentalism as an field of that is and shaped by feminist and methodologies and that challenge the entanglements between academic knowledge production and and technocratic development And while methodological these dynamics at the structural the of feminist in media and cinema by this the very a

Donald Ornstein, Louis Sucheston

A recent theorem of Orey [12] (see also [1], [6], [7], [13]) asserts that if $T$ is an $L_1$ operator induced on a discrete measure space by an irreducible recurrent aperiodic Markov matrix, then the condition (C) holds: $f \epsilon L_1, \int f = 0$ implies that $T^n f$ converges to zero in $L_1$. In an attempt to determine when (C) holds for more general operators, we at first prove the following (Theorem 1.1): Let $T$ be a positive linear contraction operator on $L_1$; if $T^nf$ and $T^{n+1}f$ intersect slightly, but uniformly in $f$ in the unit sphere of $L_1$, then $T^nf - T^{n+1}f$ converges to zero in norm. (C) follows if $T$ is conservative and ergodic (Corollary 1.3). In Section 2 we derive from this a simple proof of Orey's theorem. The main result of the paper is in Section 3 and could be called a "zero-two" theorem: Let $P(x, A)$ be a Markov kernel, and assume that there is a $\sigma$-finite measure $m$ such that for each $A, m(A) = 0$ implies $P(x, A) = 0$ a.e. and $m(A) > 0$ implies $\sum^\infty_{n=0} P^{(n)}(x, A) = \infty$ a.e. Then the total variation of the measure $P^{(n)}(x, \cdot) - P^{(n+1)}(x, \cdot)$ is either a.e. 2 for all $n$ or it converges a.e. to 0 as $n \rightarrow \infty$. In Section 4 it is shown that a version of the zero-two theorem essentially contains the Jamison-Orey generalization of Orey's theorem to Harris processes. Section 1 and Section 2 of this paper do not assume any knowledge of either operator ergodic theory or probability. Some known results in ergodic theory are applied in Section 3, but the proof of the main theorem does not depend on them.

William Michael Lloyd Holcombe

The theory of near-rings has arisen in a variety of ways. There is a natural desire to generalise the theory of rings and skew fields by relaxing some of their defining axioms. It has also been the hope of some mathematicians that certain problems in group theory, particularly
\ninvolving permutation groups and group representations, may perhaps be clarified by developing a coherent algebraic theory of near-rings. Moreover, there is an increasing recognition by mathematicians in many branches of the subject, both pure and applied, of the ubiquity of
\nnear-ring like objects.
\n
\nThe first steps in the subject were taken by Dickson and Zassenhans with their studies of 'near-fields', and by Wielandt with his classification of an important class of abstract near-rings. Papers by Frohlich, Blackett, Betsch and Laxton developed the theory considerably. Lately authors such as Beidleman, Ramakotaiah, Tharmanatram, Maxson, Malone and Clay have all added to our knowledge.
\n
\nThe history of the subject has been strongly influenced by our knowledge of ring theory, and although this has often been beneficial it must not be overlooked that a number of important problems in near-ring theory have no real parallel in the theory of rings. It is probably best to try to preserve a balance, and not to endeavour exclusively, either to generalise theorems from ring theory irrespective
\nof their usefulness, or to ignore the theory of rings and attempt to formulate a completely independent theory. In many cases our results are generalisations of theorems from ring-theory but at certain important junctures we will explicitly use the fact that we are dealing with a near-ring which is not a ring. This is a very interesting
\ndevelopment in the subject.
\n
\nWe proceed, in the first chapter, with a review of the terms and notation that will be used in this thesis.
\n
\nWhere definitions and concepts are of a specialized or technical nature and only used in one section, it seems more sensible to postpone introducing them until a more natural point in the proceedings.
\n
\nChapter 2 gives a summary of the results on the various radicals corresponding to the Jacobson radical for associative rings. Most of these results are well known and readily available in the literature. We also consider near-rings with one, or more, of these radicals zero.
\n
\nWe defined, in Chapter 1, three different types of primitive
\nnear-ring, which are all genuine generalisations of the ring theoretic concept. Of these three, the two most important are 2-primitive and 0-primitive near-rings. In Chapter 3, we examine 2-primitive near-rings with certain natural conditions imposed on them. A theorem is obtained
\nwhich could be considered to be the equivalent result for near-rings of the theorem classifying simple, artinian rings, due originally to Wedderburn and redeveloped by Jacobson.
\n
\nChapters 4 and 5 deal with 0-primitive near-rings satisfying
\ncertain conditions. Chapter 5 is a generalisation of Chapter 4, but we felt that the mathematical techniques involved would be clearer if the special case in Chapter 4 was expounded first. In these two chapters we classify a sizeable class of 0-primitive near-rings with identity.
\nand descending chain condition on right ideals.
\n
\nSeveral types of prime near-rings have been developed in the
\nliterature. In Chapter 6 we examine these and related concepts.
\n
\nIn the theory of rings, Goldies' classification of prime and
\nsemi-prime ring with ascending chain conditions, has been of immense importance. Whether such a result could be obtained in the theory of near-rings is a matter for conjecture, at the moment. We have made a start on the problem with the construction of a class of near-rings which
\nbehave in a very similar way to Prime rings with the Goldie chain conditions. This is the content of Chapter 7. The inspiration for its came mainly from the proof of Goldies' first theorem, due to C. Procesi, which is featured in Jacobson's book. (Jacobson [1]).
\n
\nChapter 8, is an attempt to initiate the development of a theory of vector groups and near-algebras which would play an important röle-in the future theory of near-rings, in a way, perhaps, similar to the Ale vector spaces and algebras play in ring theory. This may lead, in time, to results on 2-primitive near-rings with identity and a minimal right
\nideal, for example, or a Galois theory for certain 2-primitive nearrings. For the former problem, the experience of the semi-group theorists (Hoehake [1] etc. ) may prove useful.
\n
\nFinally a note on the numbering of results and definitions etc. If a reference is made, containing only two numbers, e. g. 1.12 then this means, "item 12 of section 1 of the present chapter". If a reference reads: 3.1.12, then this means "item 12 of section 1 of Chapter 3.

Kurt Kreith

1. Introduction.The classical Sturmian theorem of ordinary differential equations deals with functions u(x) and v(x) which are, respectively, solutions of differential equations(1) Um-^^j+tumO,(2) Mv=-l{J^+yv = 0.Under the assumption that "F is larger than M" (in the sense that a(x) ä a(x) > 0 and c(x) £ y(x)) one can infer information about all solutions of (2) from knowledge about a particular nontrivial solution of (1)-i.e. if u(xx) = u(x2)=0 then every solution of (2) has a zero in [xx, x2].These ideas have been generalized to second order elliptic equations by several authors ([l]-[4]) considering elliptic operators and also by Protter [5] and Swanson [6] considering the nonselfadjoint case.Given a proper relation among the coefficients of F and M and that Lu=0 has a nontrivial solution with nodal domain Ü, then it can be shown that every solution of Mv = 0 has a zero in Í2.While all the above proofs of this fact make essential use of some sort of ordering among elliptic operators, the nature of this ordering is never defined in operator-theoretic terms.The results of §2 below suggest that it is an order relationship between certain resolvents of the differential operators F and M which underlies the separation properties characteristic of Sturmian theorems.It will be shown that quite general operator equations in a Banach space 3S satisfy a type of Sturmian theorem if the operators' resolvents satisfy prescribed positivity requirements with respect to a cone SP.In order to apply this theory to differential operators, one must first establish the corresponding positivity properties for their resolvents.This is done in §3 for sufficiently regular nonselfadjoint second order elliptic operators, and the general theory of §2 is then applied in the proof of two Sturmian theorems and the establishment of criteria for certain Green's functions to be positive.

Grace Wahba

Let $\{X(t), t = \cdots -1, 0, 1, \cdots\}$ be a $P$ dimensional zero mean stationary Gaussian time series, $X(t) = \begin{pmatrix}X_1(t)\\X_2(t)\\\vdots\\X_P(t)\end{pmatrix}$ we let $R(\tau) = EX(t)X' (t + \tau)$, where $R(\tau) = \{R_{ij}(\tau), i,j = 1, 2, \cdots P\}$, and $F(\omega) = (2\pi)^{-1} \sum^\infty_{\tau=-\infty}e^{-i\omega\tau}R(\tau)$. It is assumed that $\sum^P_{i,j=1} \sum^\infty_{\tau=-\infty} |\tau| |R_{ij}(\tau)| < \infty$, and hence $F(\omega)$ exists and the elements possess bounded derivatives. It is further assumed that $F(\omega)$ is strictly positive definite, all $\omega$. Knowledge of $F(\omega)$ serves to specify the process. $F(\omega)$, and $S$, the covariance matrix of $x = \begin{pmatrix}x_1 \\ x_2\ \\ vdots\\x_P\end{pmatrix}$, a Normal $(0, S)$ random vector are known to enjoy many analogous properties. (See [7].) To cite two examples, the hypothesis that $X_i(s)$ is independent of $X_j(t)$ for $i \neq j = 1, 2, \cdots P$, any $s, t$, is equivalent to the hypothesis that $F(\omega)$ is diagonal, all $\omega$, while the hypothesis that $x_i$ is independent of $x_j$, for $i \neq j = 1, 2, \cdots P$ is equivalent to the hypothesis that $S$ is diagonal. The conditional expectation of $x_1$, given $x_2, \cdots x_P$ is \begin{equation*}E(x_1\mid x_2, \cdots x_P) = S_{12}S^{-1}_{22}\begin{pmatrix}x_2 \\ \vdots \\ x_P\end{pmatrix}, S = \bigg(\begin{array}{c|c} S_{11} & S_{12} \\ \hline S_{21} & S_{22}\end{array} \bigg)\end{equation*}. The corresponding regression problem for stationary Gaussian time series goes as follows. If \begin{equation*}E\{X_1(t)\mid X_2(s), \cdots X_P(s), s = \cdots -1, 0, 1, \cdots\} = \sum^P_{j=2} \sum^\infty_{s=-\infty} b_j(t - s)X_j(s)\end{equation*} then $B(\omega)$, defined by $B(\omega) = (B_2(\omega), \cdots B_P(\omega)), B_j(\omega) = \sum^\infty_{s=-\infty} b_j(s)e^{i\omega s}$ satisfies \begin{equation*}B(\omega) = F_{12}(\omega)F_{22}^{-1}(\omega), \quad F(\omega) = \bigg(\begin{array}{c|c}f_{11}(\omega) & F_{12}(\omega) \\ \hline F_{21}(\omega) & F_{22}(\omega)\end{array} \bigg).\end{equation*} It is interesting to ask how well these and similar analogies carry over to sampling theory and hypothesis testing. Goodman [3] gave a heuristic argument to support the conclusion that $\hat{F}_X(\omega_k)$, a suitably formed estimate of the spectral density matrix $F(\omega_k)$ has the complex Wishart distribution. The question is met here by the following results. Firstly if $\hat{F}_X(\omega_l), l = 1, 2, \cdots M$ are estimates of the spectral density matrix, each consisting of averages of $(2n + 1)$ periodograms based on a record of length $T$, with the $\omega_l$ equally spaced and $(2n + 1)M \leqq \frac{1}{2} T$, then it is possible to construct, on the same sample space as $X(t), M$ independent complex Wishart matrices $\hat{F}{\bar{\bar{X}}}(\omega_l), l = 1, 2, \cdots M$ such that $\{\hat{F}_X(\omega_l), l = 1, 2, \cdots M\}$ converge simultaneously in mean square to $\{\hat{F}_{\bar{\bar{X}}}(\omega_l), l = 1, 2,\cdots M\}$, as $n, M$ get large. Secondly, it is legitimate to use the natural analogies from multivariate analysis to test hypotheses about time series. One example is presented, as follows. The likelihood ratio test statistic for testing $S$ diagonal is $|\hat{S}|/\mathbf{\prod}^P_{i=1} \hat{s}_{ii}$ where $\hat{S} = \{\hat{s}_{ij}$ is the sample covariance matrix. The analogous statistic $\psi$ for testing $X_i(s), X_j(t)$ independent, $i,j 1 = 2, \cdots P$ from a record of length $T$ is $\psi = \prod^M_{l=1} \lbrack|\hat{F}_X(\omega_l)|/\prod^P_{i=1} \hat{f}_{ii}(\omega_l)\rbrack$ where $\hat{F}_X(\omega_l) = \{\hat{f}_{ij}(\omega_l)\}$ are the sample spectral density matrices as above. Letting ${\bar{dbar{\psi}}} = \prod^M_{l=1} \lbrack|\hat{F}_{\bar{\bar{x}}}(\omega_l)|/\prod^P_{i=1} \hat{h}_{ii}(\omega_l)\rbrack$ where $\hat{F}_{\bar{\bar{x}}}(\omega_l) = \{\hat{h}_{ij}(\omega_l)\}$ are the independent complex Wishart matrices referred to above, we show $EC_{n,M} |\log \psi - \log {\bar{\bar{\psi}}} \rightarrow 0$ for large $n, M$, where $C_{n,M}$ are chosen to make the result non-trival. The method of proof applies to any statistic which is a product over $l$ of sufficiently smooth functions of the entries of $\hat{F}_X(\omega_l)$. Applications to estimation and testing in the regression problem will appear elsewhere [8]. The distribution theory of functions of complex Wishart matrices has been well investigated by a number of authors [3] [5] [6], and hence can be easily applied here to statistics like ${\bar{\bar{\psi}}}$. The results above are shown for $P = 2$, it is clear that the proofs extended to any (fixed) finite $P$. The proofs proceed as follows, via a theorem which has somewhat more general application. For each $T$, let $X$ be the $2 \times T$ random matrix $X = \binom{X_1}{X_2} = \begin{pmatrix}X_1(1), \cdots, X_1(T)\\X_2(1), \cdots, X_2(T)\end{pmatrix}$ and let the $2T \times 2T$ covariance matrix $\Sigma$ be given by $\Sigma = \begin{pmatrix}\sum_{11} \sum_{12} \\ \sum_{21} \sum_{22}\end{pmatrix}$ where $\Sigma_{ij} = EX_i'X_j. \{\hat{F}_X(\omega_l)\}$, the sample spectral density matrices described above based on a record of length $T$, are each of the form $\hat{F}_X(\omega_l) = T^{-1}XQX'$ where $Q$ is a $T \times T$ circulant matrix with largest eigenvalue $ = T(2n + 1)^{-1} \leqq \frac{1}{2}M < <T$. We define circulant matrices $\bar{\Sigma}_{ij}$ which approximate $\Sigma_{ij}$, and a random matrix $\bar{X}$ on the sample space of $X$, $\bar{X} = \binom{\bar{X}_1}{\bar{X}_2} = \begin{pmatrix}\bar{X}_1(1), \cdots, \bar{X}_1(T)\\\bar{X}_2(1), \cdots, \bar{X}_2(T)\end{pmatrix}$ with $E\bar{X}_i'\bar{X}_j = \bar\Sigma_{ij}$. The $2T$ eigenvalues of the block circulant matrix $\bar\Sigma = \begin{pmatrix}\bar\Sigma_{11} \bar\Sigma_{12} \\ \bar\Sigma_{21} \bar\Sigma_{22}\end{pmatrix}$ will be the $2T$ eigenvalues of the $T$ matrices $\{F(2\pi j/T),j = 1, 2, \cdots T\}$. The distribution of random matrices of the form $T^{-1}\bar{X}Q\bar{X}'$ where $Q$ is any circulant matrix are relatively simple to investigate due to the fact that all circulant matrices commute, and their eigenvalues may be exhibited as simple functions of the elements. Circulant quadratic forms in random vectors with circulant covariance matrices are well known in the literature, (See [1] and references cited there). Let $\hat{F}_{X,Q} = T^{-1}XQX'$ and $\hat{F}_{\bar{X},Q} = T^{-1}\bar{X}Q\bar{X}'$ where $Q$ is now any $T \times T$ (real or complex) quadratic form with largest absolute eigenvalue $\leqq q$. The main Theorem allows the replacement of $X$ by $\bar{X}$ in the analysis, and is, that under the assumptions on $F(\omega)$ and $R(\tau)$, for any $T$, \begin{equation*}\tag{1.1} E \operatorname{tr} (\hat{F}_{X,Q} - \hat{F}_{\bar{X},Q})(\hat{F}_{X,Q} - \hat{F}_{\bar{X}, Q})^{\ast'} \leqq cq^2/T^2\end{equation*} where $c$ is a constant depending only on $F(\omega)$ and $R(\tau)$. A lemma, essentially allowing the replacement of $F(\omega)$ by a suitably chosen step-function, together with the application of (1.1) gives the results concerning the $\{\hat{F}_X(\omega_l)\}$ an $\lambda$. Since $\hat{R}(\tau)$, the sample (circularized) autocorrelation function is also of the form $T^{-1}XQX'$ with $Q$ circulant we obtain an easy corollary on the distribution of $\{\hat{R}(\tau)\}$.

Lucien Chincholle

A gas or vapor bubble moving in translation in a liquid and varying its volume propels itself by a rocket effect, which occurs in foams moving in pressure or temperature fields with a non-zero gradient. It is notably observed in boiling and centrifugal pump operation, which latter features the following two characteristic bubble types : __ 1. Gas bubbles, which are apt to emerge faster from the pump than the liquid; 2. Vapor bubbles (cavitalion). When a bubble in translatory motion implodes, energy is transferred: potential pressure energy is converted info kinetic implosion energy, which in turn becomes kinetic translation energy. The instrument for this energy transfer process is a "micro-jet" following the bubble. It is shown that a considerable increase in kinetic translation energy density occurs, which is converted into potential pressure energy on impact against a solid obstacle. The resulting pressures (10,000 kg/sq.cm) explain the mechanical aspect of cavitation erosion. Several experimental results have confirmed these theoretical considerations. The development of a rotoscope is also described, this being a device enabling a centrifugal pump impeller (for example) to be "stopped" so that only the relative motion of the flow particles remains. Unlike with a stroboscope, time exposures can he taken with this device. With more thorough knowledge of foam mechanisms, and especially of cavitalion bubble behavior, it should be possible to design cavitation erosion-proof impeller blades.

John G. Thompson

No abstract is available for this record.

John Van Ryzin

This paper is concerned with repetitive sequential play in finite statistical games (decision problems) from the statistician's point of view. We shall assume that the statistician's move at stage $k$ may depend on the previous $k - 1$ moves of Nature as well as the random variable $\mathbf{X}_k = (X_1, \cdots, X_k)$, where the $X_i$ are independent observations (r.v.'s) (possibly vector-valued) from the sequence of statistical games, $k = 1, 2, \cdots$. The play is repetitive in the sense that each component game is identical in structure, with only the moves of the statistician and Nature changing. Furthermore, we impose no assumptions regarding the behavior of the parameter sequence of Nature's moves. The statistician does have the added disadvantage that the finite class of distributions in the component game is not fully specified. However, he does know that class in question has: either (i) all members with discrete distributions or (ii) all members with $q$-dimensional a.e. continuous Lebesgue densities. This same problem when the distributions are fully known has been treated in [6] for statistical as well as more general games in which Nature's space is finite. In the case where the distributions are completely specified but the history of the past moves is unknown to the statistician, see [20], [22], [27], and [28]. The development in this paper is closely connected to and motivated by these results, particularly those of the preceding paper [27]. If for fixed $N$, the empirical distribution $p_N$ of Nature's moves is known, then the statistician could use as a rule for each of the $N$ component games a strategy Bayes against $p_N$ having risk $\phi(p_N)$. In all the papers cited in the previous paragraph, the aim was to construct for the statistician, when $p_N$ is unknown and $N$ not specified, a sequence of randomized decision functions whose $N$th average loss minus $\phi(p_N)$ approaches zero (or has an upper bound approaching zero) in a suitable sense as the number of repetitions of play, $N$, increases. However, in the case of statistical games, all of the above results require that the finite class of distributions be fully specified. In this paper we remove that assumption by estimating the distributions sequentially based on past moves and observations. Then in the present play of the component game the statistician substitutes these estimators into a procedure which is Bayes against the empirical distribution of Nature's previous moves. The resulting sequence of procedures is shown to be "asymptotically good" in the sense that the average loss over the $N$ games $W_N$ minus the Bayes risk $\phi(p_N)$ approaches zero (in an appropriate sense) as $N$, the number of games played, increases. In Section 2 we introduce notation and preliminaries. Section 3 discusses play in repetitive games and defines the proposed sequential procedures $\mathbf{t} = \{\mathbf{t}_k\}$. In Section 4 we prove preliminary results upon which all proofs are founded. Section 5 considers the discrete case giving uniform (in sequences of Nature's moves) convergence theorems (as $N \rightarrow \infty$) for the quantity $W_N - \phi(p_N)$. Theorem 5.1 is a uniform convergence theorem of $O(N^{-\frac{1}{2}})$ of the expected value of $W_N - \phi(p_N)$ for finite discrete classes, each member of which is non-degenerate and satisfies a certain tail probability condition. Under the same conditions, Theorem 5.2 gives uniform convergence to zero in probability for the quantity $N^{\frac{1}{2}} (\log N)^{-1} \{W_N - \phi(p_N)\} \text{as} N \rightarrow \infty$. Uniform convergence of $W_N - \phi(p_N) \rightarrow 0$ in probability for general non-degenerate finite discrete class is presented in Theorem 5.3. Section 6 treats the estimation problem for densities needed to form the randomized strategy sequences $\mathbf{t}$ in the continuous case. The results stated are based on a paper by Cacoullos [3] generalizing the univariate results of Parzen [15]. In Section 7, we present results for the continuous case. Theorem 7.1 and its corollary give uniform convergence of $W_N - \phi(p_N)$ to zero in probability and of its expectation to zero, respectively. The finite continuous classes of Theorem 7.1 are very general in the sense that each member is a continuous a.e. density. Finally, in Section 8 we draw certain conclusions and relate our results to similar results obtained elsewhere. The novelty of the paper rests in the fact that through the past history of Nature's moves and the observations connected with past play, one can construct a sequential strategy, $\mathbf{t} = \{\mathbf{t}_k\}$, with very little knowledge about the finite class of distributions, which approaches asymptotic "optimal" play. The lack of knowledge on the finite class of distributions distinguishes this work from the related "repetitive type" problems in games and/or decision theory treated in [1], [2], [4], [6], [7], [8], [9], [10], [12], [17], [18], [19], [20], [21], [22], [24], [25], [26], [27], [28], and [29]. For possible applications of this work see Neyman [14], especially his Example 3 and his discussion relating to the work of Blackwell [2].

R. N. Bradt

Professor Keeping's book is a text for a one-year course (90-100 hours) for students having a knowledge of elementary calculus-second or third year students.It is unusually complete in that it is difficult to think of a topic which is not treated, at least briefly, but which one might like to see included in such a course.As would be expected of a widely ranging book at this level, many results are stated without proof but it is by no means a " how to do it" book.In addition to the usual elementary probability theory, standard distributions, and classical estimation and testing, one finds, e.g. the cumulants and Ar-statistics, sampling techniques, sequential and nonparametric procedures, fixed, random and mixed models as well as latin square and incomplete block designs considered, and a last chapter which looks at multivariate problems and introduces stochastic processes.There is a laudable concern for the power of the tests discussed and the required non-central distributions are introduced.Appropriate tables, a large number of exercises (with answers) and a thirty page appendix on various mathematical topics are included as well.The price paid for the virtue of comprehensiveness is, of course, the brevity of some particular parts; one cannot have everything.However, one might reasonably suggest that the briefer the treatment the more precise should be the statements.This book is somewhat marred by puzzling, misleading, or false statements, e.g. both the sample and population moments are defined to be the " rth moment of X about zero"; "If T is sufficient, so is any function of T" (p.125); the variance of a maximum likelihood estimator is asserted to be the Cramer-Rao lower bound; in discussing the Mann-Whitney U-test, it is not clear at given points just what alternatives are being considered and while one statistic is described as the test statistic, we are instructed to reject for small values of another.