On some transducer equivalence problems for families of languages

References

• Aho , A. V. and Ullman , J. D. 1972 . The Theory of Parsing, Translation and Compiling , Vol. I , Englewood Cliffs, N.J : Prentice-Hall .
   Google Scholar
• Albert , J. and Culik , K. II . 1980 . Test sets for homomorphism equivalence on context-free languages . Inform. and Control , 45 : 273 – 284 .
   Google Scholar
• Albert , J. , Culik , K. II and Karhumäki , J. 1982 . Test sets for context free languages and algebraic systems of equations over a free monoid . Inform. and Control , 52 : 172 – 186 .
   Google Scholar
• Berstel , J. 1979 . Transductions and Context-Free Languages Stuttgart B. G. Teubner
   Google Scholar
• Blattner , M. and Head , T. 1977 . Single-valued a-transducers . J. Comput. System Sci. , 15 : 310 – 327 .
   Google Scholar
• Blattner , M. and Head , T. 1979 . The decidability of equivalence for deterministic finite transducers . J. Comput. System Sci. , 19 : 45 – 49 .
   Google Scholar
• Brandenburg , F.-J. 1980 . Multiple equality sets and Post machines . J. Comput. System Sci. , 21 : 292 – 316 .
   Google Scholar
• Culik , K. II . 1979 . Some decidability results about regular and pushdown translations . Inform. Process. Lett. , 8 : 5 – 8 .
   Google Scholar
• Culik , K. II and Karhumäki , J. 1986 . The equivalence of finite valued transducers (on HDTOL languages) is decidable . Lecture Notes Comput. Sci. , 233 : 264 – 272 .
   Google Scholar
• Culik , K. II and Salomaa , A. 1978 . On the decidability of homomorphism equivalence for languages . J. Comput. System Sci. , 17 : 163 – 175 .
   Google Scholar
• Engelfriet , J. and Rozenberg , G. 1979 . Equality languages and fixed point languages . Inform. Control , 43 : 20 – 49 .
   Google Scholar
• Engelfriet , J. and Rozenberg , G. 1980 . Fixed point languages, equality languages, and representation of recursively enumerable languages . J. Assoc. Comput. Mach. , 27 : 499 – 518 .
   Web of Science ®Google Scholar
• Ginsburg , S. 1975 . Algebraic and Automata-Theoretic Properties of Formal Languages , Amsterdam : North-Holland .
   Google Scholar
• Greibach , S. A. 1968 . A note on undecidable properties of formal languages . Math. Systems Theory , 2 : 1 – 6 .
   Google Scholar
• Greibach , S. A. 1975 . One counter languages and the IRS condition . J. Comput. System Sci. , 10 : 237 – 247 .
   Google Scholar
• Griffiths , T. V. 1968 . The unsolvability of the equivalence problem for A-free non-deterministic generalized machines . J. Assoc. Comput. Mach. , 15 : 409 – 413 .
   Google Scholar
• Gurari , E. 1982 . The equivalence problem for deterministic two-way transducers is decidable . SIAM J. Comput. , 11 : 448 – 452 .
   Google Scholar
• Gurari , E. 1985 . Two-way counter machines and finite-state transducers . Internat. J. Comput. Math. , 17 : 229 – 236 .
   Web of Science ®Google Scholar
• Hopcroft , J. E. and Ullman , J. D. 1979 . Introduction to Automata Theory, Languages, and Computation , Reading, Mass : Addison-Wesley .
   Google Scholar
• Ibarra , O. H. 1978 . The unsolvability of the equivalence problem for ε-free NGSM's with unary input (output) alphabet and applications . SIAM J. Comput. , 7 : 524 – 532 .
   Google Scholar
• Ibarra , O. H. 1982 . 2DST mappings on languages and related problems . Theoret. Comput. Sci. , 19 : 219 – 227 .
   Google Scholar
• Karhumäki , J. and Kleijn , H. C. M. 1985 . On the equivalence of compositions of morphisms and inverse morphisms on regular languages . RAIRO Inform. Théor. , 19 : 203 – 211 .
   Google Scholar
• Karhumäki , J. and Maon , Y. 1986 . A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language . J. Comput. System Sci. , 32 : 315 – 322 .
   Google Scholar
• Karhumäki , J. and Wood , D. 1984 . Inverse morphic equivalence on languages . Inform. Process. Lett. , 19 : 213 – 218 .
   Google Scholar
• Latteux , M. 1977 . Produit dans le cône rationnel engendre par D ∗ 1 . Theoret. Comput. Sci. , 5 : 129 – 134 .
   Google Scholar
• Latteux , M. 1979 . Cônes rationnels commutatifs . J. Comput. System Sci. , 18 : 307 – 333 .
   Google Scholar
• Maon , Y. 1985 . On the equivalence problem of compositions of morphisms and inverse morphisms on context-free languages . Theoret. Comput. Sci. , 41 : 105 – 107 .
   Google Scholar
• Maon , Y. 1986 . On the equivalence of some transductions involving letter to letter morphisms on regular languages . Acta Inform. , 23 : 385 – 396 .
   Google Scholar
• Restivo , A. and Reutenauer , C. 1984 . On cancellation properties of languages which are supports of rational power series . J. Comput. System Sci. , 29 : 153 – 159 .
   Google Scholar
• Salomaa , A. 1973 . Formal Languages , New York : Academic Press .
   Google Scholar
• Salomaa , A. 1978 . Equality sets for homomorphisms of free monoids . Acta Cybernet , 4 : 127 – 139 .
   Google Scholar
• Salomaa , A. and Soittola , M. 1978 . Automata-Theoretic Aspects of Formal Power Series , Berlin, Heidelberg, New York : Springer-Verlag .
   Google Scholar
• Schützenberger , M. P. 1975 . Sur les relations rationnelles . Lecture Notes Comput. Sci. , 33 : 209 – 213 .
   Google Scholar
• Turakainen , P. 1969 . Generalized automata and stochastic languages . Proc. Amer. Math. Soc. , 21 : 303 – 309 .
   Google Scholar
• Turakainen , P. 1981 . On some bounded semiAFLs and AFLs . Inform. Sci. , 23 : 31 – 48 .
   Google Scholar
• Turakainen , P. 1983 . A machine-oriented approach to compositions of morphisms and inverse morphisms . Bull. European Assoc. Theoret. Comput. Sci. , 20 : 162 – 166 .
   Google Scholar
• Turakainen , P. 1984 . Transducers and compositions of morphisms and inverse morphisms . Ann. Univ. Turku. Ser. A I , 186 : 118 – 128 .
   Google Scholar
• Turakainen , P. 1985 . A note on test sets for R-rational languages . Bull. European Assoc. Theoret. Comput. Sci. , 25 : 40 – 42 .
   Google Scholar