It is shown that for every context free language L there effectively exists a test set F, that is, a finite subset F of L such that, for any pair (g, h) of morphisms, g(x) = h(x) for all x in F implies g(x) = h(x) for all x in L. This result was claimed earlier but a detailed correct proof is given here. Together with very recent results on systems of equations over a free monoid this result implies that every algebraic system of equations is equivalent to a finite subsystem
We show that for every context free language L over some alphabet \gE there effectively exists a tes...
AbstractEhrenfeucht's Conjecture states that each subset S of a finitely generated free monoid has a...
AbstractWe present a simple construction of linear size test sets for regular languages and of singl...
It is shown that for every context free language L there effectively exists a test set F, that is, a...
AbstractEhrenfeucht's conjecture states that every language L has a finite subset F such that, for a...
AbstractEhrenfeucht's conjecture states that every language L has a finite subset F such that, for a...
We show that for every context free language L over some alphabet \gE there effectively exists a tes...
AbstractWe prove that if x0u1ix1u2ix2 = y0v1iy1v2iy2 holds for all i ϵ {0, 1, 2, 3}, then it is true...
AbstractSeveral observations concerning equations over monoids of finite sets of words are made. Mon...
AbstractEhrenfeucht's Conjecture, that each subset S of a finitely generated free monoid has a finit...
AbstractWe survey recent results on the so-called Ehrenfeucht Conjecture which states: For each lang...
AbstractA test set for a language L is a finite subset T of L with the property that each pair of mo...
This thesis considers notions of recognisability for languages over (universal) algebras. The main m...
AbstractDominoes over a free monoid and operations on them are introduced. Related algebraic systems...
AbstractFor strings υ and w define υ⩽w if and only if υ is a scattered substring of w. We give a gen...
We show that for every context free language L over some alphabet \gE there effectively exists a tes...
AbstractEhrenfeucht's Conjecture states that each subset S of a finitely generated free monoid has a...
AbstractWe present a simple construction of linear size test sets for regular languages and of singl...
It is shown that for every context free language L there effectively exists a test set F, that is, a...
AbstractEhrenfeucht's conjecture states that every language L has a finite subset F such that, for a...
AbstractEhrenfeucht's conjecture states that every language L has a finite subset F such that, for a...
We show that for every context free language L over some alphabet \gE there effectively exists a tes...
AbstractWe prove that if x0u1ix1u2ix2 = y0v1iy1v2iy2 holds for all i ϵ {0, 1, 2, 3}, then it is true...
AbstractSeveral observations concerning equations over monoids of finite sets of words are made. Mon...
AbstractEhrenfeucht's Conjecture, that each subset S of a finitely generated free monoid has a finit...
AbstractWe survey recent results on the so-called Ehrenfeucht Conjecture which states: For each lang...
AbstractA test set for a language L is a finite subset T of L with the property that each pair of mo...
This thesis considers notions of recognisability for languages over (universal) algebras. The main m...
AbstractDominoes over a free monoid and operations on them are introduced. Related algebraic systems...
AbstractFor strings υ and w define υ⩽w if and only if υ is a scattered substring of w. We give a gen...
We show that for every context free language L over some alphabet \gE there effectively exists a tes...
AbstractEhrenfeucht's Conjecture states that each subset S of a finitely generated free monoid has a...
AbstractWe present a simple construction of linear size test sets for regular languages and of singl...