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

Hamiltonicitydisconnectivityinductive definitionEhrenfeucht-Fraissé gamesgraphs with distinguished elementgraphs with successorinductive definability over finite structuresstructures without successor

Mathematics Subject Classification ID

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

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

(23)

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

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)