Second-order and Inductive Definability on Finite Structures

DOI10.1002/MALQ.19870330107MaRDI QIDQ3797174zbMATH OpenOpenAlexFDO

Authors Michel de Rougemont

Publication date 1987

Published in Zeitschrift für Mathematische Logik und Grundlagen der Mathematik (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19870330107

zbMATH Keywords

disconnectivityEhrenfeucht-Fraissé gamesgraphs with distinguished elementgraphs with successorHamiltonicityinductive definability over finite structuresinductive definitionstructures without successor

Mathematics Subject Classification ID

Inductive definability (03D70) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)

Recommendations

• On the definability of properties of finite graphs
• The functional dimension of inductive definitions
• The Complexity of Defining a Relation on a Finite Graph
• Reachability is harder for directed than for undirected finite graphs
• On winning Ehrenfeucht games and monadic NP

Cited in

(24)

• Descriptive characterizations of computational complexity
• An analysis of fixed-point queries on binary trees
• The functional dimension of inductive definitions
• Infinitary logics and 0-1 laws
• The quantifier structure of sentences that characterize nondeterministic time complexity
• On winning strategies in Ehrenfeucht-Fraïssé games
• A restricted second order logic for finite structures
• First-order spectra with one binary predicate
• How to define a linear order on finite models
• Tree-width and the monadic quantifier hierarchy.
• The closure of monadic NP
• On winning Ehrenfeucht games and monadic NP
• Arity and alternation in second-order logic
• Inductive definitions over finite structures
• One unary function says less than two in existential second order logic
• European Summer Meeting of the Association for Symbolic Logic, (Logic Colloquium '87), Granada, Spain, 1987
• Reachability is harder for directed than for undirected finite graphs
• Second-Order Algebraic Theories
• Second Order Definability Via enumerations
• scientific article; zbMATH DE number 1302495 (Why is no real title available?)
• Graph connectivity, monadic NP and built-in relations of moderate degree
• Infinitary logic for computer science
• Reconstructing structures with the strong small index property up to bi-definability
• NP-completeness by first-order and quantifier-free interpretations and related topics

This page was built for publication: Second-order and Inductive Definability on Finite Structures

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