Universal Recursively Enumerable Sets of Strings

DOI10.1007/978-3-540-85780-8_13MaRDI QIDQ3533008zbMATH OpenOpenAlexDBLPWikidataFDO

Authors André Nies, Ludwig Staiger, Cristian S. Calude, Frank Stephan

Publication date 30 October 2008

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85780-8_13

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursively (computably) enumerable sets and degrees (03D25) Turing machines and related notions (03D10)

Recommendations

• Universal recursively enumerable sets of strings
• Completely recursively enumerable sets
• Enumerating the strings of regular languages
• A class of recursively enumerable sets
• scientific article; zbMATH DE number 3974323
• Recursively EnumerableL-Sets
• scientific article; zbMATH DE number 3954889
• On a Class of Recursively Enumerable Sets
• On recursively enumerable structures
• scientific article; zbMATH DE number 4210127

Cites work

• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 1911266 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• Algorithmic Information Theory
• Classical recursion theory. The theory of functions and sets of natural numbers
• Computability and Randomness
• Information-theoretic characterizations of recursive infinite strings
• On universal computably enumerable prefix codes
• Process complexity and effective random tests
• Randomness and recursive enumerability
• Randomness and reducibility
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• The definition of random sequences

Cited in

(10)

• On universal computably enumerable prefix codes
• Effective bounds for convergence, descriptive complexity, and natural examples of simple and hypersimple sets
• scientific article; zbMATH DE number 19776 (Why is no real title available?)
• Embedding recursive functions in universal algorithms
• Not every domain of a plain decompressor contains the domain of a prefix-free one
• Simplicity via provability for universal prefix-free Turing machines
• Universality probability of a prefix-free machine
• A computation model with automatic functions and relations as primitive operations
• Universal recursively enumerable sets of strings
• scientific article; zbMATH DE number 3974323 (Why is no real title available?)

This page was built for publication: Universal Recursively Enumerable Sets of Strings

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