scientific article
From MaRDI portal
Publication:4058132
zbMath0303.68035MaRDI QIDQ4058132
Publication date: 1974
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Classical first-order logic (03B10) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Other classical first-order model theory (03C68)
Related Items
Expressiveness of Logic Programs under the General Stable Model Semantics ⋮ Universal quantifiers and time complexity of random access machines ⋮ Computing queries with higher-order logics ⋮ Multiple Usage of Random Bits in Finite Automata ⋮ Relativization of Gurevich’s Conjectures ⋮ The complexity class θp2: Recent results and applications in AI and modal logic ⋮ A Parameterized Halting Problem ⋮ An algebra and a logic for \(NC^ 1\) ⋮ A Logical Characterization of Small 2NFAs ⋮ Unnamed Item ⋮ Polynomial approximation: a structural and operational study. (Abstract of thesis) ⋮ On completeness for NP via projection translations ⋮ The expressive power of unique total stable model semantics ⋮ Descriptive complexity of deterministic polylogarithmic time and space ⋮ Extensions of an idea of McNaughton ⋮ Complexity of proving program correctness ⋮ On the approximability of the maximum common subgraph problem ⋮ Capturing complexity classes with Lindström quantifiers ⋮ On parallel hierarchies and R ki ⋮ Computation models and function algebras ⋮ Comparing the power of monadic NP games ⋮ Indistinguishability and First-Order Logic ⋮ First-order Logic with Connectivity Operators ⋮ NP for Combinatorialists ⋮ On the Variable Hierarchy of First-Order Spectra ⋮ Inductive definitions in logic versus programs of real-time cellular automata ⋮ Capturing the polynomial hierarchy by second-order revised Krom logic ⋮ Forbidden lifts (NP and CSP for combinatorialists) ⋮ On the Descriptive Complexity of Linear Algebra ⋮ Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP ⋮ Implicit representation of relations ⋮ Many Facets of Dualities ⋮ Unnamed Item ⋮ Polynomial hierarchy graph properties in hybrid logic ⋮ A characterization of definability of second-order generalized quantifiers with applications to non-definability ⋮ Computing on structures ⋮ An analysis of the Core-ML language: Expressive power and type reconstruction ⋮ Tailoring recursion for complexity ⋮ Automated reformulation of specifications by safe delay of constraints ⋮ Compiling problem specifications into SAT ⋮ Linear Programming Tools for Analyzing Strategic Games of Independence-Friendly Logic and Applications ⋮ On the CSP Dichotomy Conjecture ⋮ Graph Connectivity, Monadic NP and built-in relations of moderate degree ⋮ Implicit definability and infinitary logic in finite model theory ⋮ A restricted second order logic for finite structures ⋮ Metafinite model theory ⋮ MNP: A class of NP optimization problems ⋮ Safe Recursion Over an Arbitrary Structure: PAR, PH and DPH ⋮ Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs ⋮ The complexity of random ordered structures ⋮ Expressibility of Higher Order Logics ⋮ The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ Choiceless Computation and Symmetry ⋮ Implicit complexity over an arbitrary structure: Quantifier alternations ⋮ The Descriptive Complexity of the Deterministic Exponential Time Hierarchy ⋮ A model-theoretic characterization of constant-depth arithmetic circuits ⋮ On the computational consequences of independence in propositional logic ⋮ Independence-friendly logic without Henkin quantification ⋮ Circuit complexity and the expressive power of generalized first-order formulas ⋮ Expressivity and Complexity of Dependence Logic ⋮ On the parameterized complexity of graph modification to first-order logic properties ⋮ On the Descriptive Complexity of Color Coding ⋮ Counting of Teams in First-Order Team Logics ⋮ Fixed-Point Definability and Polynomial Time ⋮ A Logical Characterization of Small 2NFAs ⋮ Axiomatizing Rectangular Grids with no Extra Non-unary Relations ⋮ Logic and Complexity in Cognitive Science ⋮ Complexity classes and theories of finite models ⋮ Regular Graphs and the Spectra of Two-Variable Logic with Counting ⋮ An Infinitary System for the Least Fixed-Point Logic restricted to Finite Models ⋮ Unnamed Item ⋮ Asymptotic invariants, complexity of groups and related problems ⋮ Logics which capture complexity classes over the reals ⋮ On second-order generalized quantifiers and finite structures ⋮ Invariance properties of RAMs and linear time ⋮ Existential monadic second order logic on random rooted trees ⋮ Describing parameterized complexity classes ⋮ Tree-like parse and polynomial subclasses of search problems ⋮ One unary function says less than two in existential second order logic ⋮ The monadic second order logic of graphs. VI: On several representations of graphs by relational structures ⋮ Closure properties of locally finite \(\omega\)-languages ⋮ Finding a minimal 1-DNF consistent with a positive sample is LOGSNP-complete ⋮ Henkin quantifiers and complete problems ⋮ A logical approach to locality in pictures languages ⋮ Generalized quantifiers and pebble games on finite structures ⋮ The computational complexity of approximating the minimal perturbation scaling to achieve instability in an interval matrix ⋮ On the separability of subproblems in Benders decompositions ⋮ Multiple total stable models are definitely needed to solve unique solution problems ⋮ A logical characterization of constant-depth circuits over the reals ⋮ Counting quantifiers, successor relations, and logarithmic space ⋮ The expressive powers of stable models for bound and unbound DATALOG queries ⋮ Recursion theoretic characterizations of complexity classes of counting functions ⋮ Directions in generalized quantifier theory ⋮ MNP: A class of NP optimization problems ⋮ How to define a linear order on finite models ⋮ Complexity of admissible rules ⋮ Expressiveness and complexity of graph logic ⋮ Graph properties checkable in linear time in the number of vertices ⋮ On parallel hierarchies and \(R_k^i\) ⋮ Enumerating teams in first-order team logics ⋮ On winning Ehrenfeucht games and monadic NP ⋮ Normal forms for second-order logic over finite structures, and classification of NP optimization problems ⋮ Descriptive characterizations of computational complexity ⋮ Metafinite model theory ⋮ Circumscribing DATALOG: expressive power and complexity ⋮ 0-1 laws by preservation ⋮ Queries with arithmetical constraints ⋮ Extensions of MSO and the monadic counting hierarchy ⋮ A theoretical framework for knowledge-based entity resolution ⋮ Model-checking hierarchical structures ⋮ Equilibrium semantics of languages of imperfect information ⋮ First-order spectra with one variable ⋮ A second-order system for polytime reasoning based on Grädel's theorem. ⋮ Coherence and computational complexity of quantifier-free dependence logic formulas ⋮ Inclusion and exclusion dependencies in team semantics -- on some logics of imperfect information ⋮ Number of quantifiers is better than number of tape cells ⋮ 0-1 laws and decision problems for fragments of second-order logic ⋮ Max NP-completeness made easy ⋮ Colouring, constraint satisfaction, and complexity ⋮ A survey on the structure of approximation classes ⋮ Distinguishing string selection problems. ⋮ Upper and lower bounds for first order expressibility ⋮ Arithmetizing uniform \(NC\) ⋮ Why not negation by fixpoint? ⋮ On the expressive power of database queries with intermediate types ⋮ A note on the approximation of the MAX CLIQUE problem ⋮ An analysis of fixed-point queries on binary trees ⋮ An NP-complete language accepted in linear time by a one-tape Turing machine ⋮ A gentle introduction to applications of algorithmic metatheorems for space and circuit classes ⋮ Expressive power and abstraction in Essence ⋮ Optimization, approximation, and complexity classes ⋮ Approximate solution of NP optimization problems ⋮ A note on the number of monadic quantifiers in monadic \(\Sigma ^{1}_{1}\) ⋮ The descriptive complexity of decision problems through logics with relational fixed-point and capturing results ⋮ The invariant problem for binary string structures and the parallel complexity theory of queries ⋮ On approximating the longest path in a graph ⋮ Capturing complexity classes by fragments of second-order logic ⋮ A note on the descriptive complexity of maximization problems ⋮ Finite-model theory -- A personal perspective ⋮ Efficient solutions for the far from most string problem ⋮ Quantifiers and approximation ⋮ The intractability of computing the Hamming distance ⋮ On the hardness of maximum rank aggregation problems ⋮ Partition semantics for relations ⋮ The polynomial-time hierarchy ⋮ Complexity classes for self-assembling flexible tiles ⋮ Mathematical logic and quantum finite state automata ⋮ Negation in rule-based database languages: A survey ⋮ On winning strategies in Ehrenfeucht-Fraïssé games ⋮ Logic, semigroups and automata on words ⋮ Reflective relational machines ⋮ A restricted second order logic for finite structures ⋮ On Horn spectra ⋮ Partially ordered connectives and monadic monotone strict NP ⋮ Expressive power and complexity of partial models for disjunctive deductive databases ⋮ Exploiting functional dependencies in declarative problem specifications ⋮ Complexity classes and fragments of C ⋮ Counting problems over the reals ⋮ The closure of monadic NP ⋮ Structure and complexity of relational queries ⋮ A logic-based approach to incremental reasoning on multi-agent systems ⋮ Using model theory to find decidable and tractable description logics with concrete domains ⋮ On the definability of properties of finite graphs ⋮ Succinctness as a source of complexity in logical formalisms ⋮ Complexity and expressive power of deterministic semantics for DATALOG\(^ \neg\). ⋮ ASNP: a tame fragment of existential second-order logic ⋮ Functional queries in datalog ⋮ Context-sensitive transitive closure operators ⋮ Expressiveness of concept expressions in first-order description logics ⋮ Lower bound results on lengths of second-order formulas ⋮ Logical and schematic characterization of complexity classes ⋮ Computation on structures. Behavioural theory, logic, complexity ⋮ Complete problems in the first-order predicate calculus
