Two decidability problems for infinite words

DOI10.1016/0020-0190(86)90058-XzbMath0587.68072MaRDI QIDQ1072715

F. Gire

Publication date: 1986

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

zbMATH Keywords

Post correspondence problememptiness probleminfinitary languageinfinitary rational relationomega-equality set

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (9)

Two Effective Properties of ω-Rational Functions ⋮ On computability of data word functions defined by transducers ⋮ Infinite trees and automaton-definable relations over \(\omega\)-words ⋮ THREE APPLICATIONS TO RATIONAL RELATIONS OF THE HIGH UNDECIDABILITY OF THE INFINITE POST CORRESPONDENCE PROBLEM IN A REGULAR ω-LANGUAGE ⋮ Unnamed Item ⋮ Automata, Borel functions and real numbers in Pisot base ⋮ How to decide continuity of rational functions on infinite words ⋮ Determinization of transducers over finite and infinite words. ⋮ The exact complexity of the infinite Post Correspondence Problem

Cites Work

• Unnamed Item
• Relations rationnelles infinitaires
• Adherences of languages
• Some decidability results about regular and pushdown translations
• Equivalence problems for mappings on infinite strings

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