Unity of Logic and Computation
Springer International Publishing (Verlag)
978-3-031-36977-3 (ISBN)
The 23 full papers and 13 invited papers included in this book were carefully reviewed and selected from 51 submissions. They were organized in topical sections as follows: Degree theory; Proof Theory; Computability; Algorithmic Randomness; Computational Complexity; Interactive proofs; and Combinatorial approaches.
Degree theory.- Cupping computably enumerable degrees simultaneously.- The relationship between local and global structure in the enumeration degrees.- A directed system of Scott ideals.- Proof Theory.- The non-normal abyss in Kleene's computability theory.- A Constructive Picture of Noetherianity and Well Quasi-Orders.- Computability.- Symmetry for transfinite computability.- All Melodies are Lost -- Recognizability for weak and strong -ITRMs.- The de Groot dual of represented spaces.- Algorithmic Randomness.- Some Games on Turing Machines and Power from Random Strings.- Inequalities for entropies and dimensions.- Computational Complexity.- Elementarily traceable irrational numbers.- Logic vs topology on regular -languages.- Subrecursive Graphs of Representations of Irrational Numbers.- On the complexity of learning programs.- The Weihrauchcomplexity of the supergraph problem.- Extending Wagner's hierarchy to Deterministic Visibly Pushdown Automata.- On guarded extensions of MMSNP.- Turning block-sequential automata networks into smaller parallel networks with isomorphic limit dynamics.- Interactive proofs.- Structural Complexity of Rational Interactive Proofs.- Physical Zero-Knowledge Proof for Ball Sort Puzzle.- Combinatorial approaches.- Graph subshifts.- Improved Complexity Analysis of Quasi-Polynomial Algorithms Solving Parity Games.- An O( k)-approximation algorithm for minimum power k edge disjoint st-paths.
Erscheinungsdatum | 20.07.2023 |
---|---|
Reihe/Serie | Lecture Notes in Computer Science |
Zusatzinfo | LI, 297 p. 32 illus., 11 illus. in color. |
Verlagsort | Cham |
Sprache | englisch |
Maße | 155 x 235 mm |
Gewicht | 536 g |
Themenwelt | Informatik ► Theorie / Studium ► Algorithmen |
Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik | |
Schlagworte | Architecting • Artificial Intelligence • Automata Theory • computer metatheory • Databases • Engineering • Formal Languages |
ISBN-10 | 3-031-36977-7 / 3031369777 |
ISBN-13 | 978-3-031-36977-3 / 9783031369773 |
Zustand | Neuware |
Haben Sie eine Frage zum Produkt? |
aus dem Bereich