Listing graphs that satisfy first-order sentences

DOI10.1016/S0022-0000(05)80057-1zbMath0921.03041OpenAlexW2059565406MaRDI QIDQ1337473

Leslie Ann Goldberg

Publication date: 4 December 1994

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(05)80057-1

zbMATH Keywords

almost-sure sentencefirst-order language of graphsgraph listing algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Model theory of finite structures (03C13)

Related Items

On enumerating monomials and other combinatorial structures by polynomial interpolation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On generating all maximal independent sets
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• On sets polynomially enumerable by iteration
• Computation times of NP sets of different densities
• Properties of almost all graphs and complexes
• A zero-one law for logic with a fixed-point operator
• Efficient algorithms for listing unlabeled graphs
• Probabilities on finite models
• Efficient Algorithms for Listing Combinatorial Structures
• Turing machines and the spectra of first-order formulas
• Toward a Theory of Enumerations