Fixed point languages of rational transductions

DOI10.1007/BF02573161MaRDI QIDQ1822509zbMATH OpenOpenAlexFDO

Authors Wit Foryś

Publication date 1986

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/134837

zbMATH Keywords

context-sensitive languagefixed point languagefixed pointsqualitative theory of equation in free monoidsrational relationsrational transductions

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45)

Review text

This paper studies fixed points of rational transductions (rational relations). The set of fixed points of a rational transduction as a subset of a free monoid is called a fixed point language. Here we prove that a fixed point language is always a context-sensitive language and study some special cases. The results may also be viewed as a contribution to the qualitative theory of equation in free monoids.

Recommendations

• scientific article; zbMATH DE number 897896
• On fixed points of rational transductions
• scientific article; zbMATH DE number 45433
• Comment on a remark of Forys
• scientific article; zbMATH DE number 3926275

Cites work

• Equality languages and fixed point languages
• Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
• scientific article; zbMATH DE number 3654376 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3710436 (Why is no real title available?)
• scientific article; zbMATH DE number 3714977 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Sur diverses familles de langages fermées par transduction rationnelle
• Transductions des langages de Chomsky

Cited in

(13)

• The greatest fixed-points and rational omega-tree languages
• On fixed points of rational transductions
• Comment on a remark of Forys
• scientific article; zbMATH DE number 3926275 (Why is no real title available?)
• On the usefulness of bifaithful rational cones
• scientific article; zbMATH DE number 45433 (Why is no real title available?)
• Closure under union and composition of iterated rational transductions
• scientific article; zbMATH DE number 2087210 (Why is no real title available?)
• Some Characterization of Recursively Enumerable Sets
• scientific article; zbMATH DE number 897896 (Why is no real title available?)
• New types of automata to solve fixed point problems
• On the difference set of two transductions
• A fixed point characterization of cofinite languages

This page was built for publication: Fixed point languages of rational transductions

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