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 (only showing first 100 items - show all)
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 ⋮ Semiring reasoning frameworks in AI and their computational complexity ⋮ Independence-friendly logic without Henkin quantification ⋮ Circuit complexity and the expressive power of generalized first-order formulas ⋮ Generalized implicit definitions on finite structures ⋮ The expressive power of ``possible-is-certain semantics (extended abstract) ⋮ Theoretical computer science: computational complexity ⋮ Constraint satisfaction, graph isomorphism, and the pebbling comonad ⋮ Separating LREC from LFP ⋮ 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
This page was built for publication:
