Narrow Results

In a recent paper, Altenbernd, Thomas and Wöhrle have considered acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with the usual acceptance conditions, such as the Büchi and Muller ones, firstly used for infinite words. The authors asked for comparing the tiling system acceptance with an acceptance of pictures row by row using an automaton model over ordinal words of length ω². We give in this paper a solution to this problem, showing that all languages of infinite pictures which are accepted row by row by Büchi or Choueka automata reading words of length ω² are Büchi recognized by a finite tiling system, but the converse is not true. We give also the answer to two other questions which were raised by Altenbernd, Thomas and Wöhrle, showing that it is undecidable whether a Büchi recognizable language of infinite pictures is E-recognizable (respectively, A-recognizable).

We formalize the hairpin inverted repeat excision, which is known in ciliate genetics as an operation on words and languages by defining as the set of all words xαy^Rα^Rz where w = xαyα^Rz and the pointer α is in P. We extend this concept to language families which results in families . For and be the families of finite, regular, context-free, context-sensitive or recursively enumerable language, respectively, we determine the hierarchy of the families and compare these families with those of the Chomsky hierarchy. Furthermore, we present the status of decidability of the membership problem, emptiness problem and finiteness problem for the families .

We consider transition P systems as originally defined in the seminal paper of Gh. Păun, where he introduced the field of membrane computing. We show that it is decidable to determine, given a P system Π, whether it is strongly reversible (i.e., every configuration has at most one direct predecessor), resolving in the affirmative a recent open problem in the field. We also show that the set of all direct predecessors of a given configuration in a P system is an effectively computable semilinear set, which can effectively be expressed as a Presburger formula, strengthening an early result in the literature. We also prove other related results.

It was noticed by Harel in [Har86] that "one can define -complete versions of the well-known Post Correspondence Problem". We first give a complete proof of this result, showing that the infinite Post Correspondence Problem in a regular ω-language is -complete, hence located beyond the arithmetical hierarchy and highly undecidable. We infer from this result that it is -complete to determine whether two given infinitary rational relations are disjoint. Then we prove that there is an amazing gap between two decision problems about ω-rational functions realized by finite state Büchi transducers. Indeed Prieur proved in [Pri01, Pri02] that it is decidable whether a given ω-rational function is continuous, while we show here that it is -complete to determine whether a given ω-rational function has at least one point of continuity. Next we prove that it is -complete to determine whether the continuity set of a given ω-rational function is ω-regular. This gives the exact complexity of two problems which were shown to be undecidable in [CFS08].

We continue our investigation [S. Beier, M. Holzer: Properties of right one-way jumping finite automata. In Proc. 20th DCFS, LNCS, 2018] on (right) one-way jumping finite automata (ROWJFAs), a variant of jumping automata, which is an automaton model for discontinuous information processing. Here we focus on decision problems for ROWJFAs. It turns out that most problems such as, e.g., emptiness, finiteness, universality, the word problem and variants thereof, closure under permutation, etc., are decidable. Moreover, we show that the containment of a language within the strict hierarchy of ROWJFA permutation closed languages induced by the number of accepting states as well as whether permutation closed regular or jumping finite automata languages can be accepted by ROWJFAs is decidable, too. On the other hand, we prove that for (linear) context-free languages the corresponding ROWJFA acceptance problem becomes undecidable. Moreover, we discuss also some complexity results for the considered decision problems.

We prove two new effective properties of rational functions over infinite words which are realized by finite state Büchi transducers. Firstly, for each such function $F:{\mathrm{\Sigma }}^{\omega }\to {\mathrm{\Gamma }}^{\omega }$, one can construct a deterministic Büchi automaton ${𝒜}$ accepting a dense ${\mathrm{\Pi }}_2^0$-subset of ${\mathrm{\Sigma }}^{\omega }$ such that the restriction of $F$ to $L({𝒜})$ is continuous. Secondly, we give a new proof of the decidability of the first Baire class for synchronous $\omega$-rational functions from which we get an extension of this result involving the notion of Wadge classes of regular $\omega$-languages.

We introduce a combinatorial version of Stallings–Bestvina–Feighn–Dunwoody folding sequences. We then show how they are useful in analyzing the solvability of the uniform subgroup membership problem for fundamental groups of graphs of groups. Applications include coherent right-angled Artin groups and coherent solvable groups.

There is a quadratic-time algorithm that determines conjugacy between finite subsets in any torsion-free hyperbolic group. Moreover, in any k-generator, δ-hyperbolic group Γ, if two finite subsets A and B are conjugate, then x^-1 Ax = B for some x ∈ Γ with ǁxǁ less than a linear function of max{ǁγǁ : γ ∈ A ∪ B}. (The coefficients of this linear function depend only on k and δ.) These results have implications for group-based cryptography and the geometry of homotopies in negatively curved spaces.

In an appendix, we give examples of finitely presented groups in which the conjugacy problem for elements is soluble but the conjugacy problem for finite lists is not.

Geometric methods proposed by Stallings for treating finitely generated subgroups of free groups were successfully used to solve a wide collection of decision problems for free groups and their subgroups.

In the present paper we employ the generalized Stallings' folding method, developed by the author, to introduce a procedure, which has given a subgroup H of a free product of finite groups reads off its Kurosh decomposition from the subgroup graph of H.

We study the way in which the abstract structure of a small overlap monoid is reflected in, and may be algorithmically deduced from, a small overlap presentation. We show that every C(2) monoid admits an essentially canonical C(2) presentation; by counting canonical presentations we obtain asymptotic estimates for the number of non-isomorphic monoids admitting a-generator, k-relation presentations of a given length. We demonstrate an algorithm to transform an arbitrary presentation for a C(m) monoid (m at least 2) into a canonical C(m) presentation, and a solution to the isomorphism problem for C(2) presentations. We also find a simple combinatorial condition on a C(4) presentation which is necessary and sufficient for the monoid presented to be left cancellative. We apply this to obtain algorithms to decide if a given C(4) monoid is left cancellative, right cancellative or cancellative, and to show that cancellativity properties are asymptotically visible in the sense of generic-case complexity.

This paper deals with the representation and solution of asymmetric Bayesian decision problems. We present a formal framework, termed asymmetric influence diagrams. The framework is based on the syntax and semantics of the traditional influence diagram, and allows an efficient representation of asymmetric decision problems. As opposed to existing frameworks, the asymmetric influence diagram primarily encodes asymmetry at the qualitative level and it can therefore be read directly from the model.

We give an algorithm for solving asymmetric influence diagrams. The algorithm initially decomposes the asymmetric decision problem into a structure of symmetric subproblems organized as a tree. A solution to the decision problem can then be found by propagating from the leaves towards the root using existing evaluation methods to solve the subproblems.

Decision makers often face complicated decision problems with intangible and conflicting criteria. Numerous multi-criteria decision-making (MCDM) methods have been proposed to handle the measurement of the priorities of conflicting tangible/intangible criteria and in turn use them to choose the best alternative for a decision. However, the presence of many MCDM methods bewilders users. The existence of these methods becomes a decision problem in itself, and decision makers may be uncertain about which one to use. Thus the comparative analysis and evaluation of various MCDM methods has come under scrutiny by both researchers and practitioners in order to discover if there are logical, mathematical, social or practical reasons why one method is better than another. Criteria for their evaluation are the first important issue that needs to be resolved. In this paper, 16 criteria are introduced that may be used to judge and evaluate various MCDM methods. The criteria proposed and some guidelines for their evaluation are given to help readers evaluate these MCDM methods.