Universal Recursively Enumerable Sets of Strings
DOI10.1007/978-3-540-85780-8_13zbMATH Open1159.68011DBLPconf/dlt/CaludeNSS08OpenAlexW1953530293WikidataQ57001614 ScholiaQ57001614MaRDI QIDQ3533008FDOQ3533008
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
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
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Process complexity and effective random tests
- A Theory of Program Size Formally Identical to Information Theory
- The definition of random sequences
- Computability and Randomness
- Classical recursion theory. The theory of functions and sets of natural numbers
- Information-theoretic characterizations of recursive infinite strings
- Randomness and reducibility
- Randomness and recursive enumerability
- Recursively enumerable reals and Chaitin \(\Omega\) numbers
- On universal computably enumerable prefix codes
- Algorithmic Information Theory
Cited In (10)
- Embedding recursive functions in universal algorithms
- Universal recursively enumerable sets of strings
- 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
- Effective bounds for convergence, descriptive complexity, and natural examples of simple and hypersimple sets
- A computation model with automatic functions and relations as primitive operations
- Title not available (Why is that?)
- On universal computably enumerable prefix codes
- Title not available (Why is that?)
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)
