Second-order and Inductive Definability on Finite Structures

DOI10.1002/MALQ.19870330107zbMATH Open0652.03032OpenAlexW2125362004MaRDI QIDQ3797174FDOQ3797174

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

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

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)

Cited In (23)

• 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.
• Title not available (Why is that?)
• Infinitary logic for computer science
• One unary function says less than two in existential second order logic
• Descriptive characterizations of computational complexity
• 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
• Graph connectivity, monadic NP and built-in relations of moderate degree

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)