We study decision problems of the form: given a regular or linear context-free language L, is there a word of a given fixed form in L, where given fixed forms are based on word operations copy, marked copy, shuffle and their combinations.

Let Fn denote the free group on n generators. It is shown to be undecidable for two morphisms g,h:Fn→F2 and a generator element a of F2, whether or not there exists an element w∈Fn such that g(w)=a and h(w)=1, where 1 is the identity element.

Denote by ш the operation of interleaving, or shuffling, of words. We prove that, given a regular language R and a letter-to-letter morphism φ, it is undecidable whether or not there exists a word ω such that ω ш φ(ω) ∩ R ≠ ø.

We give a new simplified proof for undecidability of the Bi-Infinite Post Correspondence Problem (ℤPCP). We reduce the special case of the word problem of semi-Thue systems to ℤPCP.

The simple intramolecular model for gene assembly in ciliates consists of three molecular operations based on local DNA manipulations. It was shown to predict correctly the assembly of all currently known ciliate gene patterns. Mathematical models in terms of signed permutations and signed strings proved limited in capturing some of the combinatorial details of the simple gene assembly process. A different formalization in terms of overlap-inclusion graphs, recently introduced by Brijder and Hoogeboom, proved well-suited to describe two of the three operations of the model and their combinatorial properties. We introduce in this paper an extension of the framework of Brijder and Hoogeboom in terms of directed overlap-inclusion graphs where more of the linear structure of the ciliate genes is described. We investigate a number of combinatorial properties of these graphs, including a necessary property in terms of forbidden induced subgraphs.

The relationship between the length of a word and the maximum length of its unbordered factors is investigated in this article. Consider a finite word w of length n . We call a word bordered if it has a proper prefix, which is also a suffix of that word. Let μ( w ) denote the maximum length of all unbordered factors of w , and let ∂( w ) denote the period of w . Clearly, μ( w ) ≤ ∂( w ). We establish that μ( w ) = ∂( w ), if w has an unbordered prefix of length μ( w ) and n ≥ 2μ( w ) − 1. This bound is tight and solves the stronger version of an old conjecture by Duval [1983]. It follows from this result that, in general, n ≥ 3μ( w ) − 3 implies μ( w ) = ∂( w ), which gives an improved bound for the question raised by Ehrenfeucht and Silberger in 1979.

We characterize the switching classes that do not contain an acyclic graph. The characterization is by means of a set of forbidden induced subgraphs. We prove that in addition to switches of the cycles C n for $n\geq 7$, there are only finitely many such graphs in 24 switching classes, all having at most 9 vertices. We give a representative of each of the 24 switching classes.

It is shown that the universe problem L(Aγ ) = A* is undecidable for 4-state finite automata A with integer weight function γ on its transitions. This holds even in the case, where A is acyclic and the weighting γ satisfies the unimodality condition.

For a finite set D of nodes let E2(D)={(x, y)[mid ] x, y∈D, x≠y}. We define an inversive Δ2-structure g as a function g[ratio ]E2(D)→Δ into a given group Δ satisfying the property g(x, y)= g(y, x)−1 for all (x, y)∈E2(D). For each function (selector) σ[ratio ]D→Δ there is a corresponding inversive Δ2-structure gσ defined by gσ(x, y)=σ(x)·g (x, y)·σ(y)−1. A function η mapping each g into the group Δ is called an invariant if η(gσ)=η(g) for all g and σ. We study the group of free invariants η of inversive Δ2-structures, where η is defined by a word from the free monoid with involution generated by the set E2(D). In particular, if Δ is abelian, the group of free invariants is generated by triangle words of the form (x0, x1)(x1, x2)(x2, x0).

A subset X of a 2-structure (a reversible edge-colored directed graph) g is a clan, if X cannot be distinguished by colors from outside of X. We show that if g is primitive, i.e. it has no nontrivial clans, then there exists an edge e or an end verte

The following problem is shown to be decidable.Given are homomorphisms h~ and h2 from 2" to ~* and strings a~ and a2 over 2: such that h,~(a,) is a proper prefix of h?+~(o,) for t = 1, 2 and all n -> 0; that is, for t --1, 2, h, generates from o, an infinite string at with prefixes/g/(a~) for all n -> 0. Test whether at = a2.From this result easily follows the decidability of limit language equivalence (~-eqmvalence) for D0L systems.

The following problem is shown to be decidable. Given are homomorphisms h1 and h2 from Σ* to Σ* and strings σ1 and σ2 over Σ such that hni(σi) is a proper prefix of hn+1i (σi) for i = 1, 2 and all n ≥ 0, i.e. for i = 1, 2, hi generates from σi an infinite string αi with prefixes hni(σi) for all n ≥ 0. Test whether α1 = α2. From this result easily follows the decidability of limit language equivalence (ω-equivalence) for DOL systems.