Index sets for ω‐languages

DOI10.1002/malq.200310002zbMath1031.03064OpenAlexW1981123490MaRDI QIDQ4798202

Douglas Cenzer, Jeffery B. Remmel

Publication date: 19 March 2003

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.200310002

zbMATH Keywords

index setarithmetical hierarchycomputable analysis\(\omega\)-languagelow classes

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Applications of computability and recursion theory (03D80) Recursively (computably) enumerable sets and degrees (03D25) Hierarchies of computability and definability (03D55)

Related Items

THREE APPLICATIONS TO RATIONAL RELATIONS OF THE HIGH UNDECIDABILITY OF THE INFINITE POST CORRESPONDENCE PROBLEM IN A REGULAR ω-LANGUAGE, Decision problems for Turing machines, The exact complexity of the infinite Post Correspondence Problem