Undecidability of state complexity

We consider the state complexity of compositions of regularity-preserving language operations. As our main result, we establish that determining the state complexity of an operation composed just from intersections and marked concatenations is undecidable. The proof relies on the undecidability of Hilbert's Tenth Problem. The languages used in the construction are over a fixed alphabet with at most 50 letters. We also consider some implications and generalizations, as well as discuss open problems.     

Undecidability in decentralized supervision

It is well known that supervisor synthesis problems involving partial observations generally have high computational complexity, but was only recently shown (in the preliminary version of this article) that the solvability of decentralized supervisor synthesis problems may be undecidable, even in cases where all pertinent languages are represented as finite automata. The result is established by reduction from the halting problem for Turing machines. Alternative proofs, discovered independently by other authors, employ a reduction from Post's correspondence problem.     

Undecidability of Multi-modal Hybrid Logics

This paper establishes undecidability of satisfiability for multi-modal logic equipped with the hybrid binder ↓, with respect to frame classes over which the same language with only one modality is decidable. This is in contrast to the usual behaviour of many modal and hybrid logics, whose uni-modal and multi-modal versions do not differ in terms of decidability and, quite often, complexity. The results from this paper apply to a wide range of frame classes including temporally and epistemically relevant ones.     

Undecidability in the Imitation Game

This paper considers undecidability in the imitation game, the so-called Turing Test. In the Turing Test, a human, a machine, and an interrogator are the players of the game. In our model of the Turing Test, the machine and the interrogator are formalized as Turing machines, allowing us to derive several impossibility results concerning the capabilities of the interrogator. The key issue is that the validity of the Turing test is not attributed to the capability of human or machine, but rather to the capability of the interrogator. In particular, it is shown that no Turing machine can be a perfect interrogator. We also discuss meta-imitation game and imitation game with analog interfaces where both the imitator and the interrogator are mimicked by continuous dynamical systems.     

Undecidability of restricted uniform recurrence equations

This paper shows that the computability of uniform systems of recurrence equations is undecidable even if the number of indices, the number of recurrence equations, the number of variables, and the number of different index domains are bounded by a constant. Received November 12, 1993 / April 12, 1995     

Undecidability results for deterministic communicating sequentialprocesses

A study is presented of the subset of the communicating sequential processes (CSP) formalism in which processes are described in terms of recursive equations using only constant processes, deterministic choice, parallel composition, and sequential composition. Even with this limited version, the formalism is powerful enough to model a Turing machine so that a number of important problems such as boundedness, deadlock, and reachability are undecidable. The subset of the CSP formalism that is used is described. A number of analysis problems that are common to discrete-event systems are discussed. The Turing machine is outlined. Well-known properties of Turing machines are used to derive the undecidability results. The results are compared to properties of other models     

Undecidability of the trace coding problem and some decidable cases

We introduce and investigate the notion of weak morphisms of trace monoids with the aim of dealing with the problem of deciding the existence of codings between trace monoids. We prove that this problem is not recursively enumerable, which answers the question raised by Ochma ski in 1988. On the other hand, we show its decidability when restricted to instances with domain monoids defined by acyclic dependence graphs. We also partially answer the question of Diekert from 1990 about the number of free monoids needed for encoding a given trace monoid into their direct product.     

Classes of Timed Automata and the Undecidability of Universality

Universality for deterministic Timed Automata (TA) is PSPACE-complete but becomes highly undecidable when unrestricted nondeterminism is allowed. More precisely, universality for nondeterministic TA is Π₁¹-hard and it is still open whether it is π₁¹-complete. It is interesting to note that the entire arithmetical hierarchy is contained in this computability gap between determinism and nondeterminism. In this paper we consider three types of syntactical restrictions to nondeterministic TA, which may contribute to a better understanding of the universality problem for TA. For the first two types, which are of independent interest, the universality problem is shown to be Π₁¹-complete. For the third one, universality is Π₁⁰-complete, which is the same as saying that the complementary problem is complete in the recursively enumerable class. We also show that all the restrictions define proper subclasses of the class of timed languages defined by nondeterministic TA; and establish the relationships between the classes.     

Refining the Undecidability Border of Weak Bisimilarity

Weak bisimilarity is one of the most studied behavioural equivalences. This equivalence is undecidable for pushdown processes (PDA), process algebras (PA), and multiset automata (MSA, also known as parallel pushdown processes, PPDA). Its decidability is an open question for basic process algebras (BPA) and basic parallel processes (BPP). We move the undecidability border towards these classes by showing that the equivalence remains undecidable for weakly extended versions of BPA and BPP. In fact, we show that the weak bisimulation equivalence problem is undecidable even for normed subclasses of BPA and BPP extended with a finite constraint system.     

Undecidability in Some Structures Related to Computation Theory

We show that many of the so called discrete weak semilatticesconsidered earlier in a series of author's publications havehereditary undecidable first-order theories. Since such structuresappear naturally in some parts of computation theory, we obtainseveral new undecidability results. This applies e.g. to thestructures of complete numberings, of m-degrees of index setsand of the Wadge degrees of k-partitions in the Baire spaceand -algebraic domains. Whenever possible, we try to determinealso the exact degrees of undecidability of the theories underdiscussion.     

Undecidability in the Homomorphic Quasiorder of Finite Labelled Forests

We prove that the homomorphic quasiorder of finite k-labelledforests has a hereditary undecidable first-order theory fork 3, in contrast to the known decidability result for k = 2.We establish also hereditary undecidability (again for everyk 3) of first-order theories of two other relevant structures:the homomorphic quasiorder of finite k-labelled trees, and offinite k-labelled trees with a fixed label of the root element.Finally, all three first-order theories are shown to be computablyisomorphic to the first-order arithmetic.     

Dependence in games and dependence games

In the multi-agent systems community, dependence theory and game theory are often presented as two alternative perspectives on the analysis of agent interaction. The paper presents a formal analysis of a notion of dependence between players, given in terms of standard game-theoretic notions of rationality such as dominant strategy and best response. This brings the notion of dependence within the realm of game theory providing it with the sort of mathematical foundations which still lacks. Concretely, the paper presents two results: first, it shows how the proposed notion of dependence allows for an elegant characterization of a property of reciprocity for outcomes in strategic games; and second, it shows how the notion can be used to define new classes of coalitional games, where coalitions can force outcomes only in the presence of reciprocal dependencies.     

Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth

It has recently been proved (Je?, DLT 2007) that conjunctive grammars (that is, context-free grammars augmented by conjunction) generate some non-regular languages over a one-letter alphabet. The present paper improves this result by constructing conjunctive grammars for a larger class of unary languages. The results imply undecidability of a number of decision problems of unary conjunctive grammars, as well as non-existence of a recursive function bounding the growth rate of the generated languages. An essential step of the argument is a simulation of a cellular automaton recognizing positional notation of numbers using language equations.     

Reasoning on temporal class diagrams: Undecidability results

This paper introduces a temporal class diagram language useful to model temporal varying data. The atemporal portion of the language contains the core constructors available in both EER diagrams and UML class diagrams. The temporal part of the language is able to distinguish between temporal and atemporal constructs, and it has the ability to represent dynamic constraints between classes. The language is characterized by a model-theoretic (temporal) semantics. Reasoning services as logical implication and satisfiability are also defined. We show that reasoning on finite models is different from reasoning on unrestricted ones. Then, we prove that reasoning on temporal class diagrams is an undecidable problem on both unrestricted models and on finite ones.     

过程间并发程序分析不可判定的一个新证明方法

过程间并发程序分析问题是一个不可判定问题,理解这个不可判定问题的来源是发展一个有效的分析算法的基础.现有的证明[1]通过构造三个并发任务的PCP问题实例,证明过程间并发程序分析是一个不可判定问题.利用反射的思想,仅仅用两个并发任务构造该问题的一个PCP问题实例,证明在两个并发任务的情况下,过程间并发程序分析是一个不可判定问题.     

The periodic domino problem revisited

In this article, we give a new proof of the undecidability of the periodic domino problem. Compared to previous proofs, the main difference is that this one does not start from a proof of the undecidability of the (general) domino problem but only from the existence of an aperiodic tileset.     

On the Undecidability of Implications between Embedded Multivalued Database Dependencies

The implication and finite implication problems for embedded multivalued database dependencies are both shown to be algorithmically undecidable. The proof is by an interpretation of semigroup word problems via systems of permuting equivalence relations into database dependencies. In contrast, it is shown that for each fixed premise H one has a decision procedure for implications H F.     

Undecidability of accordance for open systems with unbounded message queues

We study asynchronously communicating open systems modeled as Petri nets with an interface. An accordance preorder describes when one open system can be safely replaced by another open system without affecting some behavioral property of the overall system. Although accordance is decidable for several behavioral properties if we assume a previously known bound on the maximal number of pending messages, we show that it is not decidable without this assumption.