scientific article; zbMATH DE number 6309316

MaRDI QIDQ5166599zbMATH OpenFDO

Authors Olivier Carton

Publication date 27 June 2014

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

zbMATH Keywords

algebraic languagesalternating machinesautomatacomplexity classesdecidabilityformal languagesgrammarshierarchy theoremNP-completenessrational languagesrecursion theoremrecursive functionsrecursively enumerable languagesspace complexitytime complexityTuring machines

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 871245
• scientific article; zbMATH DE number 6790165
• Formal Languages, Formally and Coinductively
• scientific article; zbMATH DE number 2156418
• Formal languages and computation. Models and their applications
• scientific article; zbMATH DE number 4085027
• Formal languages and applications.
• Languages, Decidability, and Complexity
• Modern aspects of complexity within formal languages
• Extension complexity of formal languages

Cited in

(9)

• A survey of languages for formalizing mathematics
• Modern aspects of complexity within formal languages
• Rauzy fractal of the smallest substitution associated with the smallest Pisot number
• Yet another characterization of the Pisot substitution conjecture
• scientific article; zbMATH DE number 5593317 (Why is no real title available?)
• scientific article; zbMATH DE number 6790165 (Why is no real title available?)
• Formal Languages, Formally and Coinductively
• Many aspects of formal languages
• Computational and attribute models of formal languages

This page was built for publication:

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