Why technology matters to writing: A cyberwriter’s tale

Technology does indeed matter to writing—and in significant ways. But how it matters can vary, depending on the particular technology, the habits and attitudes of the individual writer, and the context of learning and use. Here I employ a personal narrative (“a cyberwriter’s tale”) to track my development as a writer over time—from handwriting to typewriting to cyberwriting—and to show how each new writing technology influenced my practices and products. I argue finally for a cyborgian, posthumanist view of writing technologies. Such a view does not isolate the technological tool as an abstracted machine apart from human use, but insists on defining technology as use—as the human and machine working in concert (joined at the interface) and writing in a particular social, political, and rhetorical context.     

Two- and Three-Dimensional Constructions Based on Leonardo Grids

In 1989 I made a drawing of a net on a cube, consisting of 12 lines/elements. They were connected in a way that, a couple of months later, I recognised them in 899v in Leonardo’s Codex Atlanticus. I don’t know which moment impressed me the most: my own discovery of a very simple and powerful connecting system or the discovery of the Leonardo drawings, which implied that my own discovery was in fact a rediscovery. What we see in Leonardo’s drawings are some examples of roof constructions built with a lot of straight elements. These drawings can be ‘translated’ into the following definition: On each element we define four points at some distance of each other – two points somewhere in the middle and two points closer to the ends. To make constructions with these elements we need only connect a middle point of one element to an end point of another one in a regular over-under pattern. Out of the simple definition of the elements, I designed many different patterns for my so-called “+ - - +” structures: domes, spheres, cylinders and other models were made.     

Exposing graph uniformities via algebraic specification

This survey acknowledges an intellectual debt to Bob McNaughton. In 1968 I turned my research focus to the study of structural uniformities in graphs, motivated by the desire to study theoretical aspects of data structures. The approach that I took in this study was influenced heavily by the algebra-based study of structure in finite automata initiated in the mid-1960s by Bob and others. Their successes in using the syntactic monoid of an automaton to study its structure convinced me to base my study on a monoid-theoretic specification of graphs. The study of what I termeddata graphs occupied me for the next 4–5 years; the insights garnered during that period have served me well since, in a variety of disparate contexts. Indeed, when I began to focus on the study of structural uniformities in the interconnection networks of parallel architectures, in the mid-1980s, it was second nature to me to base this study also on a monoid-theoretic specification of the graphs underlying the interconnection networks. This paper is a brief survey of the highlights of my studies of uniformities in algebraically specified graphs. It is both fitting and pleasureful to dedicate this survey to Bob McNaughton, a wise mentor and a man of vision.This work was partially supported by NSF Grant CCR-88-12567.     

The psi-cube: a bus-based cube-type clustering network for high-performance on-chip systems

This paper proposes a bus-based cube-type network, called psi-cube, that alleviates the two problems, long wires and a limited number of I/O pins, against the on-chip systems through a small diameter and dynamic clusters, respectively. The 2ⁿ-node psi-cube is organized on the sets of node-partitions produced with an extended n-bit Hamming code ψ(n, k) [M. Takesue, Ψ-Cubes: recursive bused fat-hypercubes for multilevel snoopy caches, in: Proceedings of the International Symposium on Parallel Architectures, Algorithms, and Networks, IEEE CS Press, 1999, pp. 62–67] if we connect the nodes in each partition to the bus owned by the leader of the partition. Owing to the routing between the leaders separated by the distance of 1–3, the diameter equals n/2 if n≠2^p − 1 or n/2 otherwise. The maximum bus length is O(2^p−1) or O(2^k−1) when the psi-cube is mapped onto an array. We dynamically produce separate sets of clusters for different off-chip targets such as memory blocks, so the traffic to the leaders of clusters is much smaller than in static clusters fixed in hardware. From simulation results, the psi-cube outperforms over the mesh if the bus delay is less than 4 times the mesh link’s, and the dynamic clusters increase the psi-cube bandwidth by over 60%.     

A scientific psychologistic foundation for theories of meaning

I propose, develop and defend the view that theories of meaning — for instance, a theory specifying the logical form or truth conditions of natural language sentences — should be naturalized to scientific psychological inquiry. This involves both psychologism — the claim that semantics characterizes psychological states — and scientific naturalism — the claim that semantics will depend on the data and theories of scientific psychology. I argue that scientific psychologism is more plausible than the traditional alternative, the view that a theory of meaning is a priori. After defending scientific psychologism against several objections, I offer a speculative proposal that shows how a theory of meaning can be integrated into scientific psychology.This essay is a descendant of part of my MIT doctoral dissertation. Thanks to Ned Block, Noam Chomsky, Jim Higginbotham and Bob Stalnaker for their comments and criticisms on earlier versions, and for helpful discussion of the issues.     

A Logic for Reasoning about Generic Judgments

This paper presents an extension of a proof system for encoding generic judgments, the logic FOλ^Δ of Miller and Tiu, with an induction principle. The logic FOλ^Δ is itself an extension of intuitionistic logic with fixed points and a “generic quantifier”, , which is used to reason about the dynamics of bindings in object systems encoded in the logic. A previous attempt to extend FOλ^Δ with an induction principle has been unsuccessful in modeling some behaviours of bindings in inductive specifications. It turns out that this problem can be solved by relaxing some restrictions on , in particular by adding the axiom B≡x.B, where x is not free in B. We show that by adopting the equivariance principle, the presentation of the extended logic can be much simplified. Cut-elimination for the extended logic is stated, and some applications in reasoning about an object logic and a simply typed λ-calculus are illustrated.     

Autowrite: A Tool for Term Rewrite Systems and Tree Automata

Autowrite is an experimental software tool written in Common Lisp Oriented System (CLOS) which handles term rewrite systems and bottom-up tree automata. A graphical interface written using McCLIM, (the free implementation of the CLIM specification) frees the user of any Lisp knowledge. Software and documentation can be found at http://dept-info.labri.u-bordeaux.fr/~idurand/autowrite. Autowrite was initially designed to check call-by-need properties of term rewrite systems. For this purpose, it implements the tree automata constructions used in [F. Jacquemard. Decidable approximations of term rewriting systems. In Proc. 7th RTA, volume 1103 of LNCS, pages 362–376, 1996; I. Durand and A. Middeldorp. Decidable call by need computations in term rewriting (extended abstract). In Proc. 14th CADE, volume 1249 of LNAI, pages 4–18, 1997; Irène Durand and Aart Middeldorp. On the complexity of deciding call-by-need. Technical Report 1196–98, LaBRI, 1998; T. Nagaya and Y. Toyama. Decidability for left-linear growing term rewriting systems. Information and Computation, 178(2):499–514, 2002] and many useful operations on terms, term rewrite systems and tree automata.     

Wireless network design via 3-decompositions

We consider some network design problems with applications for wireless networks. The input for these problems is a metric space (X,d) and a finite subset UX of terminals. In the Steiner Tree with Minimum Number of Steiner Points (STMSP) problem, the goal is to find a minimum size set SX−U of points so that the unit-disc graph of S+U is connected. Let Δ be the smallest integer so that for any finite VX for which the unit-disc graph is connected, this graph contains a spanning tree with maximum degree Δ. The best known approximation ratio for STMSP was Δ−1 [I.I. Măndoiu, A.Z. Zelikovsky, A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points, Information Processing Letters 75 (4) (2000) 165–167]. We improve this ratio to (Δ+1)/2+1+ε.In the Minimum Power Spanning Tree (MPST) problem, V=X is finite, and the goal is to find a “range assignment” on the nodes so that the edge set contains a spanning tree, and ∑_vVp(v) is minimized. We consider a particular case {0,1}-MPST of MPST when the distances are in {0,1}; here the goal is to find a minimum size set SV of “active” nodes so that the graph (V,E₀+E₁(S)) is connected, where , and E₁(S) is the set the edges in with both endpoints in S. We will show that the (5/3+ε)-approximation scheme for MPST of [E. Althaus, G. Calinescu, I. Măndoiu, S. Prasad, N. Tchervenski, A. Zelikovsky, Power efficient range assignment for symmetric connectivity in static ad hoc wireless networks, Wireless Networks 12 (3) (2006) 287–299] achieves a ratio 3/2 for {0,1}-distances. This answers an open question posed in [E. Lloyd, R. Liu, S. Ravi, Approximating the minimum number of maximum power users in ad hoc networks, Mobile Networks and Applications 11 (2006) 129–142].     

Dynamic Dictionary Matching in External Memory

In thedynamic dictionary matchingproblem, a dictionaryDcontains a set of patterns that can change over time under insertion and deletion of individual patterns. Given an arbitrary textT, we must efficiently list all the dictionary patterns that occur at each text position. We investigate the I/O complexity of this problem for a large dictionary that must be stored in external storage devices. By following a completely new approach, we devise an efficient solution which is based upon the SB-tree data structure (P. Ferragina and R. Grossi, 1995,in“Proc. ACM Symposium on Theory of Computing,” pp. 693–702), and a novel notion of certificate for the dictionary matching problem. Our data structure can be adapted to efficiently work in main memory and to solve other problems, thus providing a new insight into the nature of the dictionary matching problem.     

A Coalgebraic Semantics for Epistemic Programs

This paper gives a fresh look at my previous work on “epistemic actions” and information updates in distributed systems, from a coalgebraic perspective. I show that the “relational” semantics of epistemic programs, given in [BMS2] in terms of epistemic updates, can be understood in terms of functors on the category of coalgebras and natural transformations associated to them. Then, I introduce a new, alternative, more refined semantics for epistemic programs: programs as “epistemic coalgebras”. I argue for the advantages of this second semantics, from a semantic, heuristic, syntactical and proof-theoretic point of view. Finally, as a step towards a generalization, I show these concepts make sense for other functors, and that apparently unrelated concepts, such as Bayesian belief updates and process transformations, can be seen to arise in the same way as our “epistemic actions”.