Publication:4496851

zbMath1013.03001MaRDI QIDQ4496851

Stephen Semmes, Alessandra Carbone

Publication date: 20 August 2000

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Asymptotic cyclic expansion and bridge groups of formal proofs, Group cancellation and resolution, Cut and pay, A new mapping between combinatorial proofs and sequent calculus proofs read out from logical flow graphs, Logical structures and genus of proofs, Streams and strings in formal proofs., Automatic graphs and D0L-sequences of finite graphs