Investigation of binary spectra by explicit polynomial transformations of graphs

DOI10.1016/0304-3975(92)00018-MzbMath0797.03030MaRDI QIDQ1318703

Malika More

Publication date: 5 April 1994

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

polynomial transformationsspectrum of first-order sentence

Mathematics Subject Classification ID

Graph theory (05C99) Model theory of finite structures (03C13) Hierarchies of computability and definability (03D55)

Related Items

First-order spectra with one binary predicate ⋮ On spectra of sentences of monadic second order logic with counting

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• First-order spectra with one variable
• Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität
• Universal quantifiers and time complexity of random access machines
• Complexity classes and theories of finite models
• A spectrum hierarchy