Two decidability problems for infinite words

DOI10.1016/0020-0190(86)90058-XMaRDI QIDQ1072715zbMATH OpenFDO

Authors F. Gire

Publication date 1986

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

Full work available at URL https://doi.org/10.1016/0020-0190(86)90058-X

zbMATH Keywords

emptiness probleminfinitary languageinfinitary rational relationomega-equality setPost correspondence problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

The aim of the present paper is to establish the following results: 1. The emptiness problem of the \(\omega\)-equality set of two morphisms is unsolvable or, in an equivalent way, that the \(\omega\)-Post correspondence problem is unsolved. 2. The property to be functional for an infinitary rational relation is solvable.

Recommendations

• Three applications to rational relations of the high undecidability of the infinite Post correspondence problem in a regular -language
• scientific article; zbMATH DE number 5074397
• scientific article; zbMATH DE number 2051181
• scientific article; zbMATH DE number 1339972
• Decidability of the binary infinite Post Correspondence Problem

Cites work

• Adherences of languages
• Equivalence problems for mappings on infinite strings
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• Relations rationnelles infinitaires
• Some decidability results about regular and pushdown translations

Cited in

(16)

• Infinite trees and automaton-definable relations over -words
• How to decide continuity of rational functions on infinite words
• Determinization of transducers over finite and infinite words.
• On computability of data word functions defined by transducers
• The exact complexity of the infinite Post Correspondence Problem
• ON THE POWER OF COOPERATING MORPHISMS VIA REACHABILITY PROBLEMS
• scientific article; zbMATH DE number 3940748 (Why is no real title available?)
• THE EQUALITY CONDITION FOR INFINITE CATENATIONS OF TWO SETS OF FINITE WORDS
• scientific article; zbMATH DE number 2087233 (Why is no real title available?)
• Three applications to rational relations of the high undecidability of the infinite Post correspondence problem in a regular -language
• The two-cardinal problem for languages of arbitrary cardinality
• On canonical models for rational functions over infinite words
• Uniformisations of regular relations over bi-infinite words
• Automata, Borel functions and real numbers in Pisot base
• Two Effective Properties of ω-Rational Functions
• Concurrent -hyperproperties

This page was built for publication: Two decidability problems for infinite words

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