On the decidability of cryptographic protocols with open-ended data structures

Formal analysis of cryptographic protocols has concentrated mainly on protocols with closed-ended data structures, i.e., protocols where the messages exchanged between principals have fixed and finite format. In many protocols, however, the data structures used are open-ended, i.e., messages have an unbounded number of data fields. In this paper, decidability issues for such protocols are studied. We propose a protocol model in which principals are described by transducers, i.e., finite automata with output, and show that in this model security is decidable and PSPACE-hard in presence of the standard Dolev-Yao intruder.     

On the decidability of sparse univariate polynomial interpolation

We consider the problem of determining whether or not there exists a sparse univariate polynomial that interpolates a given setS={(x _i ,y _i )} of points. Several important cases are resolved, e.g., the case when thex _i's are all positive rational numbers. But the general problem remains open.     

On the expressiveness and decidability of higher-order process calculi

In higher-order process calculi, the values exchanged in communications may contain processes. A core calculus of higher-order concurrency is studied; it has only the operators necessary to express higher-order communications: input prefix, process output, and parallel composition. By exhibiting a deterministic encoding of Minsky machines, the calculus is shown to be Turing complete. Therefore its termination problem is undecidable. Strong bisimilarity, however, is shown to be decidable. Furthermore, the main forms of strong bisimilarity for higher-order processes (higher-order bisimilarity, context bisimilarity, normal bisimilarity, barbed congruence) coincide. They also coincide with their asynchronous versions. A sound and complete axiomatization of bisimilarity is given. Finally, bisimilarity is shown to become undecidable if at least four static (i.e., top-level) restrictions are added to the calculus.     

On the decidability of the sequence equivalence problem for DOL-systems

A property, called smoothness, of a family of DOL-systems is introduced. It is shown that the sequence equivalence problem is decidable for every smooth family of DOL-systems.Then a large subfamily of DOL-systems, called simple DOL-systems is shown to be smooth.     

On some decidability problems for HDOL systems with nonsingular Parikh matrices

The problem of decidability of ultimate equivalence, emptiness of intersection and finiteness of intersection for HD0L sequences the generating morphisms of which have nonsingular Parikh matrices is investigated. The first and the third of these decidability problems are shown to be closely connected with the equivalence problem for these sequences. In certain special cases the problems are proved to be solvable. A connection between the problem of effective findability of zeros in Z-rational sequences and the above problems is established (cf. [10]).     

On decidability and closure properties of language classes with respect to bio-operations

We present general results that are useful in showing closure and decidable properties of large classes of languages with respect to biologically-inspired operations. We use these results to prove new decidability results and closure properties of some classes of languages under bio-operations such hairpin-inversion, the recently studied operation of pseudo-inversion, and other bio-operations. We also provide techniques for proving undecidability results. In particular, we give a new approach for proving the undecidability of problems for which the usual method of reduction to the undecidability of the Post Correspondence Problem seems hard to apply. Our closure and decidability results strengthen or generalize previous results.     

On the complexity of the instance checking problem in concept languages with existential quantification

Most of the work regarding complexity results for concept languages consider subsumption as the prototypical inference. However, when concept languages are used for building knowledge bases including assertions on individuals, the basic deductive service of the knowledge base is the so-called instance checking, which is the problem of checking if an individual is an instance of a given concept. We consider a particular concept language, calledALE, and we address the question of whether instance checking can be really solved by means of subsumption algorithms in this language. Therefore, we indirectly ask whether considering subsumption as the prototypical inference is justified. Our analysis, carried out considering two different measure of complexity, shows that inALE instance checking is strictly harder than subsumption. This result singles out a new source of complexity in concept languages, which does not show up when checking subsumption between concepts.This work has been supported by the ESPRIT Basic Research Action N.6810-COMPULOG 2 and by the Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo of the CNR (Italian Research Council).     

On the decidability of fragments of the asynchronous π-calculus

We study the decidability of a reachability problem for various fragments of the asynchronous π-calculus. We consider the combination of three main features: name generation, name mobility, and unbounded control. We show that the combination of name generation with either name mobility or unbounded control leads to an undecidable fragment. On the other hand, we prove that name generation without name mobility and with bounded control is decidable by reduction to the coverability problem for Petri Nets.     

On decidability of monadic logic of order over the naturals extended by monadic predicates

A fundamental result of Büchi states that the set of monadic second-order formulas true in the structure (Nat,  <) is decidable. A natural question is: what monadic predicates (sets) can be added to (Nat,  <) while preserving decidability? Elgot and Rabin found many interesting predicates P for which the monadic theory of 〈Nat, <,  P〉 is decidable. The Elgot and Rabin automata theoretical method has been generalized and sharpened over the years and their results were extended to a variety of unary predicates. We give a sufficient and necessary model-theoretical condition for the decidability of the monadic theory of (Nat, <, P₁, … , P_n).We reformulate this condition in an algebraic framework and show that a sufficient condition proposed previously by O. Carton and W.Thomas is actually necessary. A crucial argument in the proof is that monadic second-order logic has the selection and the uniformization properties over the extensions of (Nat, <) by monadic predicates. We provide a self-contained proof of this result.     

On nonlinear regression estimator with denoised variables

In this paper, a class of denoised nonlinear regression estimators is suggested for a nonlinear measurement error model where the variables in error are observed together with an auxiliary variable. The programming involved in this denoised nonlinear regression estimation is relatively simple and it can be modified with a little effort from the existing programs for nonlinear regression estimation. We establish the consistency and asymptotic normality of such denoised estimators based on the least squares and M-methods. A simulation study is carried out to illustrate the performance of these estimates. An empirical application of the model to production models in economics further demonstrates the potential of the proposed modeling procedures.     

Extension of the decidability of the marked PCP to instances with unique blocks

In the Post Correspondence Problem (PCP) an instance (h,g)$(h,g)$ consists of two morphisms h$h$ and g$g$, and the problem is to determine whether or not there exists a nonempty word w$w$ such that h(w)=g(w)$h\left(w\right)=g\left(w\right)$. Here we prove that the PCP is decidable for instances with unique blocks using the decidability of the marked PCP. Also, we show that it is decidable whether an instance satisfying the uniqueness condition for continuations has an infinite solution. These results establish a new and larger class of decidable instances of the PCP, including the class of marked instances.     

On the decidability of termination of query evaluation in transitive-closure logics for polynomial constraint databases

The formalism of constraint databases, in which possibly infinite data sets are described by Boolean combinations of polynomial inequality and equality constraints, has its main application area in spatial databases. The standard query language for polynomial constraint databases is first-order logic over the reals. Because of the limited expressive power of this logic with respect to queries that are important in spatial data base applications, various extensions have been introduced. We study extensions of first-order logic with different types of transitive-closure operators and we are in particular interested in deciding the termination of the evaluation of queries expressible in these transitive-closure logics. It turns out that termination is undecidable in general. However, we show that the termination of the transitive closure of a continuous function graph in the two-dimensional plane, viewed as a binary relation over the reals, is decidable, and even expressible in first-order logic over the reals. Based on this result, we identify a particular transitive-closure logic for which termination of query evaluation is decidable and which is more expressive than first-order logic over the reals. Furthermore, we can define a guarded fragment in which exactly the terminating queries of this language are expressible.     

On the use of history variables

Summary This paper is a response to a suggestion that the use of history variables in proofs of the correctness of programs is unnecessary. It is argued that the use of history or ghost variables can be of benefit in improving the clarity of some proofs; that without their use some proofs require programming techniques which are at variance with the widely-accepted tenets of structured programming and that for some proofs of correctness their use is unavoidable.     

On the utility of procedural rules: conditions of the use of rules in the production of operation sequences

Abstract

Through a series of experiments we sought to find the conditions of identification and application of a four-level system of hierarchic rules. These rules were used to organize patterns of digits, which were copied (by our 49 subjects) from a visual display on to paper. We varied instructions in the rule system, tasks (rule application vs transfer by heart), load on the working memory, and number of repetitions of the digit transfer task. The procedure applied by the subjects was a mixture of memorization of grouped digits and rule application. The mixture depended on the ratio of costs and benefits of rule application. We found an efficient unconscious rule application existed, relieving working memory. The most extensive rule application was found with a combination of instruction on the rules and transfer by memorization. The applied model of rule hierarchy and its acquisition was determined by behavioral economy. The unconscious rule application could be systematically promoted.     

On forming joint variables in computing with words

Abstract

We discuss Zadeh’s idea of computing with words and emphasize its perspective that information provides a restriction on the values variables can assume. We describe the role that the constraint-based semantics plays in translating natural language statements into formal mathematical objects. One task that arises in using this approach is the formulation of joint restrictions on multiple variables from individual information about each of the variables. Our interest here is to extend the capability of the framework of computing with words in the task of forming joint variables with the introduction of the idea of perceived relatedness between variables, a concept closely related to the idea of correlation. We are particularly interested in role that knowledge about perceived relatedness between variables can play in further restricting the possible values of joint then that simple provided by the individual constraints. We look at the problem of joining various types of uncertain variables, possibilistic, probabilistic and Dempster-Shafer belief structures.     

On the nature of rules and conversation

The use of findings from conversation analysis in the design of human-computer interfaces and especially in the design of computer-human speech dialogues is a matter of considerable controversy. For example, in Going up a Blind Alley (Button, 1990) and On Simulacrums of Conversation (Button and Sharrock, 1995), Button argues that conversation analysis is of only limited use in the computational modelling of interaction. He suggests that computers will never be able to converse with humans because of the fundamentally different ways in which humans and computers use rules in the production of language.We show in this paper that these arguments are neither necessary nor sufficient to rule out the possibility of computers which can be said to converse. They depend on a view about the nature of rules which is based on a fundamental misunderstanding of the scope of computation. The way in which mathematical systems such as Context Free Grammars use rules is very different from the use of the rules in principle-based approaches to language or the micro-rules of neural networks. If there is a problem with conversing computers, it lies more with the true nature of the interaction that is taking place and with considerations about the nature of cognition than with the construction and use of rules.