Axiomatising tree-interpretable structures

DOI10.1007/S00224-003-1104-8MaRDI QIDQ705058zbMATH OpenOpenAlexFDO

Authors Achim Blumensath

Publication date 25 January 2005

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-003-1104-8

zbMATH Keywords

algorithmic properties of infinite structurescardinality quantifiersdecidabilitydefinabilityfinitely axiomatizableguarded logicmodel-checkingmonadic second-order logicrelational structures

Mathematics Subject Classification ID

Logic in computer science (03B70) Logic with extra quantifiers and operators (03C80) Second- and higher-order model theory (03C85) Automata and formal grammars in connection with logical questions (03D05) Specification and verification (program logics, model checking, etc.) (68Q60)

Review text

This paper is a new contribution to the study of the algorithmic properties of infinite structures. The topic is motivated by several problems in various areas of computer science. The author extends the notion of a prefix-recognizable graph to general relational structures by introducing tree-interpretable structures. The main result is that any tree-interpretable structure is finitely axiomatizable in guarded second-order logic with cardinality quantifiers, but also several other results are obtained. Moreover, the author poses some open problems.

Recommendations

• scientific article; zbMATH DE number 2086419
• Axiomatising extended computation tree logic
• Axiomatising extended computation tree logic
• An axiomatization of full computation tree logic
• Lifted inference with tree axioms
• scientific article; zbMATH DE number 475422
• Axiomatizing proof tree concepts in bounded arithmetic
• Applying tree languages in proof theory
• scientific article; zbMATH DE number 475414

Cited in

(5)

• Axiomatising extended computation tree logic
• Automatic presentations and semigroup constructions
• Simple monadic theories and partition width
• scientific article; zbMATH DE number 475414 (Why is no real title available?)
• scientific article; zbMATH DE number 2086419 (Why is no real title available?)

This page was built for publication: Axiomatising tree-interpretable structures

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