No label defined (Q3219110)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3885311
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3885311

      Statements

      0 references
      0 references
      1984
      0 references
      equivalence problem
      0 references
      rational transductions
      0 references
      decidability
      0 references
      morphisms
      0 references
      regular language
      0 references
      [For the entire collection see Zbl 0544.00022.] It is well known that the equivalence problem for rational transductions is undecidable, while it is decidable for single-valued rational transductions. We establish here a strict borderline between the decidability and the undecidability by considering the equivalence problems for rational transductions which are compositions of morphisms and inverse morphisms restricted to a given regular language. More precisely, we show that it is undecidable whether or not two transductions of the form \(h\circ g^{-1}\), where h and g are morphisms, are equivalent (word by word) on a given regular language, and that the same problem for transductions of the form \(g^{-1}\circ h\) is decidable.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references