Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe finiteness problem for automaton semigroups is undecidable
267
0
0.0
(
0
)
Added by
Pierre Gillibert
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Authors
Pierre Gillibert
Ask ChatGPT about the research
No Arabic abstract
The finiteness problem for automaton groups and semigroups has been widely studied, several partial positive results are known. However we prove that, in the most general case, the problem is undecidable. We study the case of automaton semigroups. Given a NW-deterministic Wang tile set, we construct an Mealy automaton, such that the plane admit a valid Wang tiling if and only if the Mealy automaton generates a finite semigroup. The construction is similar to a construction by Kari for proving that the nilpotency problem for cellular automata is unsolvable. Moreover Kari proves that the tiling of the plane is undecidable for NW-deterministic Wang tile set. It follows that the finiteness problem for automaton semigroup is undecidable.
rate research
Read More
This paper addresses a decision problem highlighted by Grigorchuk, Nekrashevich, and Sushchanskii, namely the finiteness problem for automaton (semi)groups. For semigroups, we give an effective sufficient but not necessary condition for finiteness and, for groups, an effective necessary but not sufficient condition. The efficiency of the new criteria is demonstrated by testing all Mealy automata with small stateset and alphabet. Finally, for groups, we provide a necessary and sufficient condition that does not directly lead to a decision procedure.
When two spatially separated parties make measurements on an unknown entangled quantum state, what correlations can they achieve? How difficult is it to determine whether a given correlation is a quantum correlation? These questions are central to problems in quantum communication and computation. Previous work has shown that the general membership problem for quantum correlations is computationally undecidable. In the current work we show something stronger: there is a family of constant-sized correlations -- that is, correlations for which the number of measurements and number of measurement outcomes are fixed -- such that solving the quantum membership problem for this family is computationally impossible. Thus, the undecidability that arises in understanding Bell experiments is not dependent on varying the number of measurements in the experiment. This places strong constraints on the types of descriptions that can be given for quantum correlation sets. Our proof is based on a combination of techniques from quantum self-testing and from undecidability results of the third author for linear system nonlocal games.
Petri nets, also known as vector addition systems, are a long established model of concurrency with extensive applications in modelling and analysis of hardware, software and database systems, as well as chemical, biological and business processes. The central algorithmic problem for Petri nets is reachability: whether from the given initial configuration there exists a sequence of valid execution steps that reaches the given final configuration. The complexity of the problem has remained unsettled since the 1960s, and it is one of the most prominent open questions in the theory of verification. Decidability was proved by Mayr in his seminal STOC 1981 work, and the currently best published upper bound is non-primitive recursive Ackermannian of Leroux and Schmitz from LICS 2019. We establish a non-elementary lower bound, i.e. that the reachability problem needs a tower of exponentials of time and space. Until this work, the best lower bound has been exponential space, due to Lipton in 1976. The new lower bound is a major breakthrough for several reasons. Firstly, it shows that the reachability problem is much harder than the coverability (i.e., state reachability) problem, which is also ubiquitous but has been known to be complete for exponential space since the late 1970s. Secondly, it implies that a plethora of problems from formal languages, logic, concurrent systems, process calculi and other areas, that are known to admit reductions from the Petri nets reachability problem, are also not elementary. Thirdly, it makes obsolete the currently best lower bounds for the reachability problems for two key extensions of Petri nets: with branching and with a pushdown stack.
By adapting the iterative yardstick construction of Stockmeyer, we show that the reachability problem for vector addition systems with a stack does not have elementary complexity. As a corollary, the same lower bound holds for the satisfiability problem for a two-variable first-order logic on trees in which unbounded data may label only leaf nodes. Whether the two problems are decidable remains an open question.
Action logic is the algebraic logic (inequational theory) of residuated Kleene lattices. This logic involves Kleene star, axiomatized by an induction scheme. For a stronger system which uses an $omega$-rule instead (infinitary action logic) Buszkowski and Palka (2007) have proved $Pi_1^0$-completeness (thus, undecidability). Decidability of action logic itself was an open question, raised by D. Kozen in 1994. In this article, we show that it is undecidable, more precisely, $Sigma_1^0$-complete. We also prove the same complexity results for all recursively enumerable logics between action logic and infinitary action logic; for fragments of those only one of the two lattice (additive) connectives; for action logic extended with the law of distributivity.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
