Some decidability results about regular and pushdown translations

DOI10.1016/0020-0190(79)90080-2zbMath0397.68083OpenAlexW2012813724MaRDI QIDQ1253937

Karel II Culik

Publication date: 1979

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(79)90080-2

zbMATH Keywords

DecidabilityContext-Free LanguagesEtol LanguagesFunctional Finite TransducerHomomorphic Equivalence On LanguagesRegular and Pushdown TranslationsUnambiguous Pushdown Transducer

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25)

Related Items (14)

The equivalence of finite valued transducers (on HDT0L languages) is decidable ⋮ Balance of many-valued transductions and equivalence problems ⋮ On some decision questions concerning pushdown machines ⋮ New techniques for proving the decidability of equivalence problem ⋮ 2DST mappings of languages and related problems ⋮ On some transducer equivalence problems for families of languages ⋮ A homomorphic characterization of time and space complexity classes of languages† ⋮ Checking sets, test sets, rich languages and commutatively closed languages ⋮ Dominoes over a free monoid ⋮ On the equivalence of some transductions involving letter to letter morphisms on regular languages ⋮ Inverse morphic equivalence on languages ⋮ An undecidable problem for context-free grammars ⋮ On the equivalence problem of compositions of morphisms and inverse morphisms on context-free languages ⋮ Two decidability problems for infinite words

Cites Work

• On the decidability of homomorphism equivalence for languages
• Optimization of LR(k) parsers
• The decidability of the equivalence problem for DOL-systems
• Unnamed Item
• Unnamed Item

This page was built for publication: Some decidability results about regular and pushdown translations