Balance of many-valued transductions and equivalence problems

DOI10.1016/0304-3975(86)90151-9MaRDI QIDQ1095671zbMATH OpenOpenAlexFDO

Authors Yael Maon, Amiram Yehudai

Publication date 1986

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(86)90151-9

zbMATH Keywords

balance of two morphismsequivalencerational transductionsregular languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

The notion of balance of two morphisms on a given language is generalized to deal with the whole family of rational transductions. The usefulness of balance for proving decidability of equivalence of rational transductions is established. In particular, an alternative proof for a result of Culik showing the decidability of the equivalence problem of single-valued rational transductions on regular languages is given. In addition, a new result showing the decidability of the equivalence problem of inverses of single-valued rational transductions on regular languages is obtained.

Recommendations

• scientific article; zbMATH DE number 2209492
• Many-Valued Logics and Translations
• scientific article; zbMATH DE number 4060732
• On the containment and equivalence problems for two-way transducers
• Equivalence problems for transducers with a bounded number of states
• scientific article; zbMATH DE number 3857068
• Decomposing Finite-Valued Transducers and Deciding Their Equivalence
• On the Decidability of the Equivalence for k-Valued Transducers
• On equivalence and uniformisation problems for finite transducers
• Equivalence of finite-valued symbolic finite transducers

Cites work

• A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language
• Alternation
• Equality languages and fixed point languages
• scientific article; zbMATH DE number 3866597 (Why is no real title available?)
• scientific article; zbMATH DE number 3970124 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• scientific article; zbMATH DE number 3633742 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 1988980 (Why is no real title available?)
• Inverse morphic equivalence on languages
• On test sets for checking morphism equivalence on languages with fair distribution of letters
• On the decidability of homomorphism equivalence for languages
• On the decidability of the sequence equivalence problem for DOL-systems
• On the equivalence of some transductions involving letter to letter morphisms on regular languages
• Some decidability results about regular and pushdown translations
• Test sets and checking words for homomorphism equivalence
• The decidability of the equivalence problem for DOL-systems
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines

Cited in

(7)

• On the equivalence of some transductions involving letter to letter morphisms on regular languages
• On the equivalence problem of compositions of morphisms and inverse morphisms on context-free languages
• Balancedness of MSO transductions in polynomial time
• Balancedness and coboundaries in symbolic systems
• scientific article; zbMATH DE number 3885311 (Why is no real title available?)
• scientific article; zbMATH DE number 978454 (Why is no real title available?)
• On the balancedness of tree-to-word transducers

This page was built for publication: Balance of many-valued transductions and equivalence problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1095671)