Partial residuated structures and quantum structures

Residuated structures, bounded commutative residuated lattices in particular, play an important role in the study of algebraic structures of logics—classical and non-classical. In this paper, by introducing partial adjoint pairs, a new structure is presented, named partial residuated lattices, which can be regarded as a version of residuated lattices in the case of partial operations, and their basic properties are investigated. The relations between partial residuated lattices and certain quantum structures are considered. We show that lattice effect algebras and D-lattices both are partial residuated lattices. Conversely, under certain conditions partial residuated lattices are both lattice effect algebras and D-lattices. Finally, dropping the assumption on commutativity, some similar results are obtained. Project supported by the NSF of China (No. 10771524).     

OnP-subset structures

Given a setA, we investigate the lattice structure formed by those of its subsets that belong to the complexity classP, taken modulo finite variations and ordered by inclusion. We show that up to isomorphism, only three structures are possible for this lattice. IfA isP-immune, itsP-subset structure degenerates to the trivial one-element lattice. IfA is almostP-immune but notP-immune (for instance, ifA is inP), itsP-subset structure is isomorphic to the countable atomless Boolean lattice. In all other cases theP-subset structure is isomorphic to ⁽⁾ , the weak countable power of. All natural intractable sets appear to fall in the third category. The results generalize to many other complexity classes, and similar characterizations hold for, e.g., the structures formed by recursive complexity cores.This research was supported in part by the Emil Aaltonen Foundation, the Academy of Finland, and the National Science Foundation under Grant No. MCS83-14272. Part of the work was carried out while the second author was visiting the Department of Mathematics, University of California at Santa Barbara.     

Synchronous structures

Synchronous languages have been designed to ease the development of reactive systems, by providing a methodological framework for assisting system designers from the early stages of requirement specifications to the final stages of code generation or circuit production. Synchronous languages enable a very high-level specification and an extremely modular design of complex reactive systems by structural decomposition of them into elementary processes. We define an order-theoretical model that gives a unified mathematical formalisation of all the above aspects of the synchronous methodology and characterises the essentials of the synchronous paradigm.     

Configuration structures, event structures and Petri nets

In this paper the correspondence between safe Petri nets and event structures, due to Nielsen, Plotkin and Winskel, is extended to arbitrary nets without self-loops, under the collective token interpretation. To this end we propose a more general form of event structure, matching the expressive power of such nets. These new event structures and nets are connected by relating both notions with configuration structures, which can be regarded as representations of either event structures or nets that capture their behaviour in terms of action occurrences and the causal relationships between them, but abstract from any auxiliary structure.A configuration structure can also be considered logically, as a class of propositional models, or—equivalently—as a propositional theory in disjunctive normal from. Converting this theory to conjunctive normal form is the key idea in the translation of such a structure into a net.For a variety of classes of event structures we characterise the associated classes of configuration structures in terms of their closure properties, as well as in terms of the axiomatisability of the associated propositional theories by formulae of simple prescribed forms, and in terms of structural properties of the associated Petri nets.     

Trust structures

A general formal model for trust in dynamic networks is presented. The model is based on the trust structures of Carbone, Nielsen and Sassone: a domain theoretic generalisation of Weeks’ framework for credential based trust management systems, e.g., KeyNote and SPKI. Collections of mutually referring trust policies (so-called “webs” of trust) are given a precise meaning in terms of an abstract domain-theoretic semantics. A complementary concrete operational semantics is provided using the well-known I/O-automaton model. The operational semantics is proved to adhere to the abstract semantics, effectively providing a distributed algorithm allowing principals to compute the meaning of a “web” of trust policies. Several techniques allowing sound and efficient distributed approximation of the abstract semantics are presented and proved correct. BRICS: Basic Research in Computer Science (www.brics.dk) funded by the Panish National Research Foundation.     

Unbounded computational structures

The concept of suspended evaluation is used as an approach to co-routines. Problems from the literature involving infinite data structures are solved in a LISP-like applicative language to demonstrate that simple new semantics can enrich old and ‘friendly’ control structures. It appears that the very nature of these problems draws control structure and data structure together, so that issues of style may be studied at once for both.     

Low-contention data structures

We consider the problem of minimizing contention in static (read-only) dictionary data structures, where contention is measured with respect to a fixed query distribution by the maximum expected number of probes to any given cell. The query distribution is known by the algorithm that constructs the data structure but not by the algorithm that queries it. Assume that the dictionary has n$n$ items. When all queries in the dictionary are equiprobable, and all queries not in the dictionary are equiprobable, we show how to construct a data structure in O(n)$O\left(n\right)$ space where queries require O(1)$O\left(1\right)$ probes and the contention is O(1/n)$O(1/n)$. Asymptotically, all of these quantities are optimal. For arbitrary   query distributions, we construct a data structure in O(n)$O\left(n\right)$ space where each query requires O(logn/loglogn)$O(logn/loglogn)$ probes and the contention is O(logn/(nloglogn))$O(logn/(nloglogn))$. The lack of knowledge of the query distribution by the query algorithm prevents perfect load leveling in this case: for a large class of algorithms, we present a lower bound, based on VC-dimension, that shows that for a wide range of data structure problems, achieving contention even within a polylogarithmic factor of optimal requires a cell-probe complexity of Ω(loglogn)$\Omega (loglogn)$.     

On higher structures

In this paper, we discuss various philosophical aspects of the hyperstructure concept extending networks and higher categories. By this discussion, we hope to pave the way for applications and further developments of the mathematical theory of hyperstructures.     

Designing overlay structures

Although overlaying code segments is a very old technique, there is very little literature ⁶⁸ on what the ground rules are, what the options are and how to select an overlay structure. As a result, the facilities provided by most linkage editors are much poorer than they need be. In this paper we define the problem, give an algorithm for obtaining ‘minimal’ overlay structures and describe the surrounding commands and environment that are necessary to turn this algorithm into a practical tool.     

Recursive data structures

The power and convenience of a programming language may be enhanced for certain applications by permitting treelike data structures to be defined by recursion. This paper suggests a pleasing notation by which such structures can be declared and processed; it gives the axioms which specify their properties, and suggests an efficient implementation method. It shows how a recursive data structure may be used to represent another data type, for example, a set. It then discusses two ways in which significant gains in efficiency can be made by selective updating of structures, and gives the relevant proof rules and hints for implementation. The examples show that a certain range of applications in symbol manipulation can be efficiently programmed without introducing the low-level concept of a reference into a high-level programming language.The work on this paper was supported in part by National Science Foundation under grant number GJ 36473X and ARPA Research Contract DAHC 15-73-0435.     

Programs to process trees,representing program structures and data structures

Utility programs discussed in this paper were initially developed to automate the ‘drawing’ of the non-binary trees which occur when using a Jackson type methodology for program design; these trees represent either data structures or program structures, showing the selective, sequential and iterative relationships between nodes First a language was developed to allow information about tree structures to be input to the programs. Techniques and algorithms are described which enabled utility programs to be coded to process this data; transforming it into printable diagrammatic representation of trees; pseudo-code representation of program trees; and PL/I or Cobol programs Secondly a merge operation for trees had to be defined, reflecting the step in Warmer's and Jackson's methodologies of combining data tree structures together to provide a program structure. Further algorithms are described which enable this step to be performed automatically, they include checks that each particular merge can be performed Because the aims and concepts have been fluid some of the ideas have been discarded, and programs have been rewritten. Valuable insights were gained from persuing both the rejected and the acceptable ideas, these are described in this paper.     

Copper-encapsulated silicon micromachined structures

Selective copper encapsulation on silicon has been used to fabricate micromachined devices such as inductors with quality factors over 30 at frequencies above 5 GHz. The devices are fabricated using either polysilicon surface micromachining, or integrated polysilicon and deep reactive ion etching bulk silicon micromachining. Their exposed silicon surfaces are selectively activated by palladium activation, which allows the subsequent copper deposition on the activated silicon surfaces only. This silicon encapsulated-with-copper technique takes advantage of both the excellent mechanical properties of silicon (to maintain structural integrity), and the high conductivity of copper (for electrical signal transmission). Furthermore, the process not only minimizes interfacial forces typical of physical metal deposition on silicon, but also balances the forces by metal encapsulation on all sides of the silicon structures     

Solving topologically modified structures

During the design process, the engineer frequently makes modifications to the structure. At times, the modification involves topological changes such as joint addition or joint deletion which result in an increase or a decrease in the size of the stiffness matrix. These modifications may not lead to a completely different configuration. In such cases the results of a previous analysis can be used to decrease the computational effort which is needed for a complete reanalysis of the modified structure.This paper presents two algorithms for obtaining the inverse of the modified stiffness matrix. The algorithms use the results of a previous solution to obtain solutions when joints are added to or deleted from a structure. The algorithm for joint addition uses Householder's identity to obtain the inverse of that portion of the modified stiffness matrix corresponding to the original stiffness matrix. The inverse of the modified stiffness matrix is then obtained by inversion by matrix partitioning. The algorithm for joint deletion uses the extraction of the inverse of a reduced matrix and Householder's identity to obtain the inverse of the modified stiffness matrix. A comparison of operation counts for the proposed algorithms and a complete inversion indicates that by using the proposed methods a 20–80 per cent saving in the computational effort is achieved.     

Processes of transforming structures

Transformations of relational structures by applying productions have been studied. Processes of transforming structures are considered and a method of composing such processes is developed. The processes generalize derivation trees of context-free grammars. The method of composing processes generalizes the operations on derivation trees. Church-Rosser properties of processes are stated.     

Associative tabular data structures

Attention is drawn to a method of implementing data structures in core memory by means of associative links instead of pointers. The properties of associative links are discussed and the way in which they may be exploited in a program for formal differentiation is illustrated. There is a section on microprogramming support for the associative search operations involved.