Publication:4496851
zbMath1013.03001MaRDI QIDQ4496851
Stephen Semmes, Alessandra Carbone
Publication date: 20 August 2000
symmetry; duality; cut elimination; graph theory; recursion; NP-completeness; proof theory; oriented graphs; finite automata; formal languages; visibility graph; complexity theory; graphs and groups; recursively presented groups; implicit definitions; complex formal objects; morphisms in logic
68Q25: Analysis of algorithms and problem complexity
05-02: Research exposition (monographs, survey articles) pertaining to combinatorics
68Q45: Formal languages and automata
68R10: Graph theory (including graph drawing) in computer science
54E35: Metric spaces, metrizability
03-02: Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
03D05: Automata and formal grammars in connection with logical questions
03D15: Complexity of computation (including implicit computational complexity)
03F05: Cut-elimination and normal-form theorems
68-02: Research exposition (monographs, survey articles) pertaining to computer science
03F07: Structure of proofs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03F20: Complexity of proofs
05Cxx: Graph theory
Related Items