scientific article; zbMATH DE number 6309316

zbMath1292.68001MaRDI QIDQ5166599

Olivier Carton

Publication date: 27 June 2014

Full work available at URL: http://www.calameo.com/read/00001585686ff5c1a1e02?authid=wuyqRHjAcA6W

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

Turing machinesautomataNP-completenessdecidabilitytime complexityformal languagesgrammarsrecursive functionsalgebraic languagesrecursively enumerable languagescomplexity classesspace complexityrecursion theoremrational languageshierarchy theoremalternating machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Algebraic theory of languages and automata (68Q70) Decidability of theories and sets of sentences (03B25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (2)

Rauzy Fractal of the Smallest Substitution Associated with the Smallest Pisot Number ⋮ Yet Another Characterization of the Pisot Substitution Conjecture

This page was built for publication: