Monadic generalized spectra

DOI10.1002/MALQ.19750210112zbMATH Open0317.02054OpenAlexW2003895694MaRDI QIDQ4078009FDOQ4078009

Authors: Ronald Fagin 

Publication date: 1975

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Other classical first-order model theory (03C68)

Cited In (51)

• The quantifier structure of sentences that characterize nondeterministic time complexity
• GAMES AND CARDINALITIES IN INQUISITIVE FIRST-ORDER LOGIC
• On the definability of properties of finite graphs
• The fine spectrum of a variety
• Infinitary logics and 0-1 laws
• The closure of monadic NP
• Monadic Second-Order Logic and Transitive Closure Logics over Trees
• On sets of relations definable by addition
• Finite-model theory -- A personal perspective
• Tree-width and the monadic quantifier hierarchy.
• Hybrid planning for challenging construction problems: an answer set programming approach
• The complexity of graph connectivity
• Descriptive complexity for counting complexity classes
• Arity bounds in first-order incremental evaluation and definition of polynomial time database queries
• Infinitary logic for computer science
• One unary function says less than two in existential second order logic
• A probabilistic view of Datalog parallelization
• Comparing the power of monadic NP games
• Fifty years of the spectrum problem: survey and new results
• A logical approach to locality in pictures languages
• Datalog extensions for database queries and updates
• A note on the number of monadic quantifiers in monadic \(\Sigma ^{1}_{1}\)
• Bounds in the propagation of selection into logic programs
• On winning strategies in Ehrenfeucht-Fraïssé games
• A Conjecture Concerning the Spectrum of a Sentence
• First-order spectra with one variable
• Generalized quantifiers and pebble games on finite structures
• Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
• Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second - Order Logic
• Partially ordered connectives and monadic monotone strict NP
• The dimension of the negation of transitive closure
• Structure and complexity of relational queries
• On winning Ehrenfeucht games and monadic NP
• Comparing the succinctness of monadic query languages over finite trees
• First order quantifiers in monadic second order logic
• Existential MSO over two successors is strictly weaker than over linear orders
• On spectra of sentences of monadic second order logic with counting
• Nonstandard methods for finite structures
• The functional dimension of inductive definitions
• First-order spectra with one binary predicate
• Computing on structures
• The monadic quantifier alternation hierarchy over grids and graphs
• Comparing the Power of Games on Graphs
• Probabilities of First-Order Sentences about Unary Functions
• Complexity classes and theories of finite models
• Almost Everywhere Equivalence of Logics in Finite Model Theory
• Monadic partition logics and finite automata
• Can datalog be approximated?
• Reachability is harder for directed than for undirected finite graphs
• Graph connectivity, monadic NP and built-in relations of moderate degree
• Generalized implicit definitions on finite structures

This page was built for publication: Monadic generalized spectra

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