Folded Hasse diagrams of combined traces

To represent concurrent behaviours one can use concepts originating from language theory, including traces and comtraces. Traces can express notions such as concurrency and causality, whereas comtraces can also capture weak causality and simultaneity. This paper is concerned with the development of efficient data structures and algorithms for manipulating comtraces. We introduce and investigate folded Hasse diagrams of comtraces which generalise Hasse diagrams defined for partial orders and traces. We also develop an efficient on-line algorithm for deriving Hasse diagrams from language theoretic representations of comtraces. Finally, we briefly discuss how folded Hasse diagrams could be used to implement efficiently some basic operations on comtraces.     

Isomorphism theorems on generalized effect algebras based on atoms

A well-known fact is that every generalized effect algebra can be uniquely extended to an effect algebra in which it becomes a sub-generalized effect algebra and simultaneously a proper order ideal, the set-theoretic complement of which is its dual poset. We show that two non-isomorphic generalized effect algebras (even finite ones) may have isomorphic effect algebraic extensions. For Archimedean atomic lattice effect algebras we prove “Isomorphism theorem based on atoms”. As an application we obtain necessary and sufficient conditions for isomorphism of two prelattice Archimedean atomic generalized effect algebras with common (or isomorphic) effect algebraic extensions.     

Metamodeling semantics of multiple inheritance

Inheritance provides object-oriented programming with much of its great reusability power. When inheritance is single, its specifications are simple and everybody roughly agrees on them. In contrast, multiple inheritance yields ambiguities that have prompted long-standing debates, and no two languages agree on its specifications. In this paper, we present a semantics of multiple inheritance based on metamodeling. A metamodel is proposed which distinguishes the “identity” of properties from their “values” or “implementations”. It yields a clear separation between syntactic and semantic conflicts. The former can be solved in any language at the expense of a common syntactic construct, namely full name qualification. However, semantic conflicts require a programmer’s decision, and the programming language must help the programmer to some extent. This paper surveys the approach based on linearizations, which has been studied in depth, and proposes some extensions. As it turns out that only static typing takes full advantage of the metamodel, the interaction between multiple inheritance and static typing is also considered, especially in the context of virtual types. The solutions proposed by the various languages with multiple inheritance are compared with the metamodel results. Throughout the paper, difficulties encountered under the open-world assumption are stressed.     

Volume discounting coordinates a supply chain effectively when demand is sensitive to both price and sales effort

In this paper, we use a simple and parsimonious model to investigate the performance of volume discounting schemes (hereafter “[VD]”) in a supply chain where the market demand is sensitive to both retail price “p” and sales effort “e” — hereafter called a “(p,e)-channel.” The problem is analyzed as a manufacturer-leading Stackelberg game. We first present, for the deterministic-system-parameter situation, contract-designing procedures under two contract formats; namely, a “regular” version of [VD] (hereafter “[RVD]”) and a “continuous” version of [VD] (hereafter “[CVD]”). Our solutions show that [RVD] cannot perfectly coordinate this (p,e)-sensitive channel; moreover, very often [RVD] leads to a lower channel efficiency than the simple price-only contract. In contrast, we show that [CVD] leads to perfect channel coordination — a significant result since most contract formats have been shown in the literature to be unable to coordinate a (p,e)-channel. Next, we consider the more realistic situations in which the manufacturer is uncertain about one of the system parameters — specifically, either the market size “a” or the effort cost “η”. Our results show that, if Manu is uncertain about a, [RVD] becomes useless but the manufacturer can still use [CVD] to benefit himself. When the manufacturer is uncertain about η, [CVD] remains useful (as expected); however, surprisingly, [RVD] can outperform [CVD] when both the mean value and the uncertainty of η are sufficient high. These results underline the necessity of evaluating a contract format under various forms of system-parameter uncertainties — often at the expense of analytical tractability.     

LMI characterization of reduced-order H∞ controllers via invariant zero structure

In this paper, we clarify a new relationship between invariant zeros of a generalized plant and the order reduction of H_∞ controllers by using linear matrix inequalities in both continuous-time and discrete-time cases. In contrast with our recent paper, where a relationship between an unstable transmission-zero structure and the H_∞ controller order reduction is initiated in a fundamental manner, results obtained in this paper are more flexible in two senses: assumptions that are made for the generalized plant are relaxed, and stable as well as unstable invariant zeros are characterized to obtain a reduced-order H_∞ controller.     

The Expressive Power of Finitely Many Generalized Quantifiers

We consider extensions of first order logic (FO) and fixed point logic (FP) by means of generalized quantifiers in the sense of Lindström. We show that adding a finite set of such quantifiers to FP fails to capture PTIME, even over a fixed signature, strengthening earlier results. We also prove a stronger version of this result for PSPACE, which enables us to establish that PSPACE ≠ FO on any infinite class of ordered structures, a weak version of the ordered conjecture formulated by Ph. G. Kolaitis and M. Y. Vardi (Fixpoint logic vs. infinitary logic in finite-model theory, in "Proceedings, 7th IEEE Symposium on Logic in Computer Science, 1992," pp. 46-57). These results are obtained by defining a notion of element type for bounded variable logics with finitely many generalized quantifiers. Using these, we characterize the classes of finite structures over which the infinitary logic L^ω_∞ω extended by a finite aw set of generalized quantifiers Q is no more expressive than first order logic extended by the quantifiers in Q.     

Choosing reference classes and building provisional models

A well-known problem in default logic is the ability of naive reasoners to explain bothg and ¬g from a set of observations. This problem is treated in at least two different ways within that camp.One approach is examination of the various explanations and choosing among them on the basis of various explanation comparators. A typical comparator is choosing the explanation that depends on the most specific observation, similar to the notion of narrowest reference class.Others examine default extensions of the observations and choose whatever is true in any extension, or what is true in all extensions or what is true in preferred extensions. Default extensions are sometimes thought of as acceptable models of the world that are discarded as more knowledge becomes available.We argue that the notions of specificity and extension lack clear semantics. Furthermore, we show that the problems these ideas were supposed to solve can be handled easily within a probabilistic framework.     

Time prediction based on process mining

Process mining allows for the automated discovery of process models from event logs. These models provide insights and enable various types of model-based analysis. This paper demonstrates that the discovered process models can be extended with information to predict the completion time of running instances. There are many scenarios where it is useful to have reliable time predictions. For example, when a customer phones her insurance company for information about her insurance claim, she can be given an estimate for the remaining processing time. In order to do this, we provide a configurable approach to construct a process model, augment this model with time information learned from earlier instances, and use this to predict e.g., the completion time. To provide meaningful time predictions we use a configurable set of abstractions that allow for a good balance between “overfitting” and “underfitting”. The approach has been implemented in ProM and through several experiments using real-life event logs we demonstrate its applicability.     

Sequences related to Legendre/Jacobi sequences

Two families of binary sequences are constructed from dth order cyclotomic generator and from dth order generalized cyclotomic generator with respect to two distinct primes respectively. By using estimates of certain exponential sums over rings or fields, the upper bounds of both the well-distribution measure and the order k (at least for small k) correlation measure of the resulting binary sequences are evaluated, and some lower bounds on the linear complexity profile of d-ary cyclotomic sequences and d-ary generalized cyclotomic sequences are presented. Our results indicate that such binary sequences possess “very good” local pseudo-randomness.     

Geodesic voting for the automatic extraction of tree structures. Methods and applications

This paper presents new methods to segment thin tree structures, which are, for example present in microglia extensions and cardiac or neuronal blood vessels. Many authors have used minimal cost paths, or geodesics relative to a local weighting potential P, to find a vessel pathway between two end points. We utilize a set of such geodesic paths to find a tubular tree structure by seeking minimal interaction. We introduce a new idea that we call geodesic voting or geodesic density. The approach consists of computing geodesics from a set of end points scattered in the image which flow toward a given source point. The target structure corresponds to image points with a high geodesic density. The “Geodesic density” is defined at each pixel of the image as the number of geodesics that pass over this pixel. The potential P is defined in such way that it takes low values along the tree structure, therefore geodesics will migrate toward this structure thereby yielding a high geodesic density. We further adapt these methods to segment complex tree structures in a noisy medium and apply them to segment microglia extensions from confocal microscope images as well as vessels.     

Evolving choice structures for genetic programming

It is quite difficult but essential for Genetic Programming (GP) to evolve the choice structures. Traditional approaches usually ignore this issue. They define some “if-structures” functions according to their problems by combining “if-else” statement, conditional criterions and elemental functions together. Obviously, these if-structure functions depend on the specific problems and thus have much low reusability. Based on this limitation of GP, in this paper we propose a kind of termination criterion in the GP process named “Combination Termination Criterion” (CTC). By testing CTC, the choice structures composed of some basic functions independent to the problems can be evolved successfully. Theoretical analysis and experiment results show that our method can evolve the programs with choice structures effectively within an acceptable additional time.     

Smart PAC-learners

The PAC-learning model is distribution-independent in the sense that the learner must reach a learning goal with a limited number of labeled random examples without any prior knowledge of the underlying domain distribution. In order to achieve this, one needs generalization error bounds that are valid uniformly for every domain distribution. These bounds are (almost) tight in the sense that there is a domain distribution which does not admit a generalization error being significantly smaller than the general bound. Note however that this leaves open the possibility to achieve the learning goal faster if the underlying distribution is “simple”. Informally speaking, we say a PAC-learner L is “smart” if, for a “vast majority” of domain distributions D, L does not require significantly more examples to reach the “learning goal” than the best learner whose strategy is specialized to D. In this paper, focusing on sample complexity and ignoring computational issues, we show that smart learners do exist. This implies (at least from an information-theoretical perspective) that full prior knowledge of the domain distribution (or access to a huge collection of unlabeled examples) does (for a vast majority of domain distributions) not significantly reduce the number of labeled examples required to achieve the learning goal.     

Product structure (BOM)-based product similarity measures using orthogonal procrustes approach

In geometry, two configurations are called similar if they can be brought to a complete match by rigid motions and dilations. In the simplest case, product designs X and Y have the same dimensionality and same number of points which can be brought into a one to one correspondence by substantive considerations. Under orthogonal transformations, product design Y can only be rotated and reflected in order to approximate product design X. As for the “as close as possible” or “relatively close” criterion, a reasonable definition would be to measure the distances between corresponding points, square these values, and add them to obtain the sum-of-squares criterion L. In this paper, a product structure (BOM)-based product similarity measures using orthogonal procrustes approach is proposed. A structural product is first transformed into bill of materials (BOM), the structural similarity measurement between a product query and target product is calculated and evaluated using orthogonal procrustes approach. The results show that the proposed product structure similarity measure method can help companies find desired product information based on BOM feature.     

An efficient approach to representation and simplification of complex networks

This paper describes an efficient approach to representation and analysis of complex networks. Typically, an n node system is represented by an n × n connection matrix. This paper presents a new connection matrix representation scheme that uses three fields; “begin node”, “end node”, and “component id” to represent each node in the network. The proposed approach to connection matrix representation is more concise than the n × n matrix, which is often sparsely populated. This paper also describes network simplification algorithm based on the revised connection matrix. The algorithm when applied to a large system with 55 tie-sets reduced the network to a single tie-set.     

The essence of eta-expansion in partial evaluation

Selective eta-expansion is a powerful binding-time improvement,i.e., a source-program modification that makes a partial evaluator yield better results. But like most binding-time improvements, the exact problem it solves and the reason why have not been formalized and are only understood by few.In this paper, we describe the problem and the effect of eta-redexes in terms of monovariant binding-time propagation: eta-redexes preserve the static data flow of a source program by interfacingstatic higher-order values in dynamic contexts anddynamic higher-order values in static contexts. They contribute to twodistinct binding-time improvements.We present two extensions of Gomard's monovariant binding-time analysis for the pure -calculus. Our extensions annotateand eta-expand -terms. The first one eta-expands static higher-order values in dynamic contexts. The second also eta-expands dynamic higher-order values in static contexts.As a significant application, we show that our first binding-time analysis suffices to reformulate the traditional formulation of a CPS transformation into a modern one-pass CPS transformer. This binding-time improvement is known, but it is still left unexplained in contemporary literature,e.g., about cps-based partial evaluation.We also outline the counterpart of eta-expansion for partially static data structures.     

A comparison of different geometrical models in calculating physicochemical properties of quaternary systems

In this paper, the geometric model has been extended to estimate the physicochemical properties of quarternary systems based on the data of its six sub-binary systems. It has been pointed out that the asymmetrical model is not suitable for the calculation of the systems higher than three components due to the difficulty of selecting the asymmetrical component. Though this difficulty will disappear in the symmetrical model, another trouble will be introduced instead. When two of “n$n$” components are identical, this symmetrical model cannot be reduced to a “n−1$n-1$” component system, of course, which is unreasonable. Based on these facts, Chou et al. have proposed a “new generation geometric model” that can overcome all these defects mentioned above. The correctness of this new generation geometric model has already been proved through a theoretical analysis and partially demonstrated by some ternary examples. However, it has never been tested in high order practical systems due to the lack of data. Recently, some volume and viscosity data in the Propan-2-ol + methylacetate + dichloromethane +n$n$-pentane quaternary system have been found that can be used to judge which model would be better. The calculation results show that in the viscosity calculation our model is the best, while in the volume calculation our model is still good, when the calculation error is considered. These facts prove that the new generation geometrical model can work well in a higher order system.     

Parallel evolutionary algorithms can achieve super-linear performance

One of the main reasons for using parallel evolutionary algorithms (PEAs) is to obtain efficient algorithms with an execution time much lower than that of their sequential counterparts in order, e.g., to tackle more complex problems. This naturally leads to measuring the speedup of the PEA. PEAs have sometimes been reported to provide super-linear performances for different problems, parameterizations, and machines. Super-linear speedup means that using “m” processors leads to an algorithm that runs more than “m” times faster than the sequential version. However, reporting super-linear speedup is controversial, especially for the “traditional” research community, since some non-orthodox practices could be thought of being the cause for this result. Therefore, we begin by offering a taxonomy for speedup, in order to clarify what is being measured. Also, we analyze the sources for such a scenario in this paper. Finally, we study an assorted set of results. Our conclusion is that super-linear performance is possible for PEAs, theoretically and in practice, both in homogeneous and in heterogeneous parallel machines.     

On ?∞, robust stability and performance with ?2 and ?∞ perturbations

In this paper we will consider systems with linear time-invariant perturbations. We will analyze robust performance in the ?₂ and ?_∞ settings. The ?₂ setting gives rise to the familiar case of structured singular values, and a stability criterion is given by the “small μ” theorem. We show that although the necessary and sufficient criterion of robust stability for the ?_∞ case (?_∞ stability with structured ?_∞-gain bounded perturbations) is the same “small μ” criterion, a system with ?₂-gain bounded perturbations is never ?_∞ stable.