NP-completeness of small conflict set generation for congruence closure

The efficiency of satisfiability modulo theories (SMT) solvers is dependent on the capability of theory reasoners to provide small conflict sets, i.e. small unsatisfiable subsets from unsatisfiable sets of literals. Decision procedures for uninterpreted symbols (i.e. congruence closure algorithms) date back from the very early days of SMT. Nevertheless, to the best of our knowledge, the complexity of generating smallest conflict sets for sets of literals with uninterpreted symbols and equalities had not yet been determined, although the corresponding decision problem was believed to be NP-complete. We provide here an NP-completeness proof, using a simple reduction from SAT.     

相位一致性的理解及两种新的相位一致性模型*

首先研究了1D方波信号边缘处的相位分布特点,发现不同频率分量在边缘处的相位不一定收敛于同一个角度值,而是会随着占空比的变化而变化。因此,基于局部能量的相位一致性模型实际上是不同频率分量利用幅度加权后的平均结果。由于在多数自然图像中,图像频率分量的幅度会随着频率的增加而呈反比下降,基于局部能量的相位一致性模型主要由低频分量决定,这样在一定程度上降低了对边缘空间定位的精度。为了提高边缘检测的空间分辨力,提出了两种新的相位一致性模型。利用二维Log Gabor 滤波器提取图像的局部相位信息,分析了利用这三种相位一致性模型进行边缘检测的结果。实验表明,利用两种新的相位一致性模型可以检测到更加细致的图像边缘信息,具有更高的边缘空间定位能力。     

STL and extensions

Three approaches to improve the free form fabrication process are discussed: (i) the use of approximation control parameters (ii) the development and use of standard transform language (STL) extensions and (iii) methods to handle exact geometrical models at the rapid prototyping (RP) level. The first two of these are concerned with improving the quality of the data exchanged, the third with improving the quality of the process itself. It is shown that the use of various STL approximation control parameters can improve the quality but does not always result in a good approximation. To improve this situation we propose two versions of an extended STL format with the following advantages: (i) smaller final models are obtained that allow faster geometry processing, (ii) the reconstruction of exact object geometry is possible which permits avoidance of volume distortion for consistent control of slice and layer approximations and (iii) a mechanism is provided that allows attachment of manufacturing information. We describe in pseudo-code and develop an ACIS implementation for the writing of the extended STL format, for the reconstruction of a solid from the extended STL file and for the consistent facetting of an exact model. Slice timing results show significant time reductions for the exact and consistent facetted models over the STL-based facetted models. The main conclusion, though, is that STL should be replaced with a STEP-based data exchange standard.     

Pascal-clarifications and recommended extensions

Summary The objectives of this paper are to clarify certain issues in the language Pascal that were left open by the defining Report and to recommend specific forms for certain extensions of the language that have repeatedly appeared in discussions and even implementations. By encouraging prospective implementors to adopt a common form, we wish to enhance the prospects for practical portability of Pascal programs. Except for parameters being procedures and functions, the language constructs described by the Pascal Report are not changed, i.e. the new syntax permits the same constructs with the same (intended) meaning. The paper expresses the author's proposal following a discussion among a small group of people who have been working on Pascal compilers and standardization. In itself it is not an attempt to standardize Pascal or present a complete revision of the Report. Concentrating on the type concept, the meaning of identifiers, and a limited number of extensions the need of which is generally accepted, the paper establishes guidelines for standardization and revision of the Pascal Report. It is presented as a carefully deliberated and (hopefully) consistent proposal for acceptance by whatever means the Pascal community may choose to adopt. I wish to thank everyone mentioned for his comments and cooperation, but above all Niklaus Wirth for his encouraging support and most valuable influence, especially in limiting the number of topics considered in detail. I thank R.D. Tennent and two anonymous referees for their valuable comments and suggestions.     

A congruence modular variety that is neither congruence distributive nor 3-permutable

We present an example of a variety of algebras which is congruence modular but not congruence distributive or congruence n-permutable for each n ≥ 2.     

Interval extensions and interval iterations

For nonlinear operators in partially ordered spaces interval extensions will be defined by means of Lipschitz operators. Assumptions are made for the inclusion monotony of these interval extensions. In this manner we obtain methods for interval iteration to include a solution of an operator equation. By transforming the equation in iterative form a parameter is chosen appropriately, so that the convergence of the interval sequence becomes as fast as possible.     

Similarity-based learning and its extensions

This paper synthesizes a number of approaches to concept representation and learning in a multilayered model. The paper emphasizes what has been called similarity-based learning (SBL) from examples, although this review is extended to address wider issues. The paper pays particular attention to requirements for incremental and uncertain environments, and to interrelationships among concept purpose, concept representation, and concept learning.
One goal of the paper is to unite some of the notions underlying recent research, in an attempt to construct a more complete and extensible framework. This framework is designed to capture representations and methods such as those based on hypothesis search and bias selection, and to extend the ideas for greater system capability. This leads to a specific perspective for multilayered learning which has several advantages, such as greater clarity, more uniform learning, and more powerful induction.
The approach clarifies and unifies various aspects of the problem of concept learning. Some results'are (1) Various concept representations (such as logic, prototypes, and decision trees) are subsumed by a standard form which is well suited to learning, particularly in incremental and uncertain environments; (2) Concept learning may be enhanced by exploiting a particular phenomenon in many spaces-this phenomenon is a certain kind of smoothness or regularity, one instance of which underlies the similarity in SBL systems; (3) The paper treats the phenomenon in a general way and applies it hierarchically. This has various advantages of uniformity. For example the model allows layered learning algorithms for concept learning all to be instantiations of one basic algorithm. A single kind of representation (an instantiation of the standard form) is prominent at each level. The combination of representation and algorithm allows fast, accurate, concise, and robust concept learning.     

Testing congruence for mobile processes

Testing equivalence on πprocesses has been studied in literature.The equivalence is not closed under the iuput prefix operator and is therefore not a congruence relation.This note takes a look at testing congruence on fipite π processes.A complete equational system is given for the congruence relation.     

An exercise in structural congruence

Milner's structural congruence is decidable for the pi-calculus without restriction, in exponential space.     

A congruence relation for sPBC

In this paper we define a congruence relation for regular terms of sPBC (stochastic Petri Box Calculus), by means of which we identify those processes that have the same behaviour, not only in terms of the multiactions that they can perform, but also taking into account the stochastic information that they have associated. In order to define this equivalence relation we have to define an adequate semantics for the synchronization operator, as well as a new labelled transition system for regular terms of sPBC.     

Characterizations and extensions of pushdown translations

A device called a pushdown assembler has been recently introduced and has been shown capable of defining exactly the syntax directed translations (SDT's). The output operation of the pushdown assembler can be extended in a natural way to obtain a more powerful device called a type B pushdown assembler (or B-machine). A B-machine can define SDT's more simply and directly than the original pushdown assembler. B-machines can also define many interesting translations which are not SDT's. In this paper the B-machine is defined and compared with the original pushdown assembler. The properties of B-machine translations are investigated and it is shown that, as with SDT's, there exists a natural infinite hierarchy of B-machine translations.     

Brownian matrices: properties and extensions

Brownian matrices arise in certain models used in digital signal processing. Fast algorithms for solving brownian systems of linear equations can be derived because any brownian matrix is congruent to a tridiagonal matrix. This, and related properties, are developed and extended to matrices having a more general patterned structure.     

Hera and other extensions of Erato

The MHD stability code ERATO has been modified in order to study helically symmetric equilibria. The resulting new code is called HERA. A new formulation to calculate the vacuum contribution has been added to the spectral codes ERATO and HERA. The finite hybrid element approach is equivalent to that in the plasma region. The stability problem including a conducting wall is now done in one step. The fast angular variation of high n modes has been eliminated by a change of variables. With this new quasi-mode representation it is possible to study unstable modes with nq values up to 1000 in the case of high β, high shear equilibria. It applies equally well to internal and external modes.     

Sharing information and building trust through value congruence

This study explores how value congruence contributes to the formation of trust in e-businesses, and how trust and value congruence influence consumers to share personal information. It is hypothesized that the perceived values of organizations regarding moral, social, environmental and political causes can have an effect on the trusting beliefs of e-commerce consumers and their willingness to disclose private personal information. A total of 775 subjects rated their perceived value congruence with organizations, their trusting beliefs, and the types of information they would be willing to disclose. This study finds that value congruence not only plays a role in mediating the trust of consumers for the organizations, but it also has a strong effect on determining their willingness to disclose personal information. In some cases, the influence of value congruence is greater than that of trust, even though trust has been touted in the literature as one of the most important factors in e-commerce. This research expands prior work by using structural equation modeling to test the relative strength of the effect of value congruence on each dimension of trust and the overall trust level, as well as its direct effect on behavioral intentions in terms of information sharing for non-profit and for-profit organizations.

分配序列效应代数的理想和同余

分配的序列效应代数（简记为DSEA）,是指在一个效应代数上带有一种乘积运算并满足一定的条件。介绍了分配的序列效应代数中的左理想、右理想、理想、素理想和同余等概念,并且证明了满足（RDP）性质并且以1为乘积单位的分配序列效应代数是具有（RDP）性质的反格分配序列效应代数的子直积。     

A note on congruence permutability and fuzzy logic

We study congruence permutability of algebras with fuzzy equalities. The notion of degree of congruence permutability naturally arises in this context. We present a Mal'cev-like characterization of congruence permutable varieties of algebras with fuzzy equalities. Our note presents a way to generalize various congruence conditions from the point of view of fuzzy logic.     

L-fuzzy congruence classes in universal algebras

In this paper, we study fuzzy congruence relations and their classes; so-called fuzzy congruence classes in universal algebras whose truth values are in a complete lattice satisfying the infinite meet distributive law. Fuzzy congruence relations generated by a fuzzy relation are fully characterized in different ways. The main result in this paper is that, we give several Mal'cev-type characterizations for a fuzzy subset of an algebra $A$ in a given variety to be a class of some fuzzy congruence on $A$. Some equivalent conditions are also given for a variety of algebras to possess fuzzy congruence classes which are also fuzzy subuniverses. Special fuzzy congruence classes called fuzzy congruence kernels are characterized in a more general context in universal algebras.     

Branching bisimulation congruence for probabilistic systems

A notion of branching bisimilarity for the alternating model of probabilistic systems, compatible with parallel composition, is defined. For a congruence result, an internal transition immediately followed by a non-trivial probability distribution is not considered inert. A weaker definition of branching bisimilarity for the same model has been given earlier. Here we show that our branching bisimulation is the coarsest congruence for parallel composition that is included in the weaker version. To support the use of the present equivalence as a reduction technique, we also show that probabilistic CTL formulae are preserved by our equivalence, and we provide a polynomial-time algorithm deciding branching bisimilarity.