Program schemes, arrays, Lindström quantifiers and zero-one laws
From MaRDI portal
Publication:1606129
DOI10.1016/S0304-3975(01)00183-9zbMath1018.03023OpenAlexW1997448383MaRDI QIDQ1606129
Publication date: 31 July 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00183-9
Logic in computer science (03B70) Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)
Related Items
Using Program Schemes to Capture Polynomial-Time Logically on Certain Classes of Structures, Program Schemes with Deep Pushdown Storage, On the power of deep pushdown stacks
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The expressive power of stratified logic programs
- Some relationships between logics of programs and complexity theory
- Persistence of vector replacement systems is decidable
- Datalog extensions for database queries and updates
- Infinitary logics and 0-1 laws
- Using the Hamiltonian path operator to capture NP
- An observation on time-storage trade off
- Complexity of some problems in Petri nets
- On the power of built-in relations in certain classes of program schemes
- Context-sensitive transitive closure operators
- Logical and schematic characterization of complexity classes
- On locating cubic subgraphs in bounded-degree connected bipartite graphs
- Structure and complexity of relational queries
- Adding for-loops to first-order logic
- Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
- Arity hierarchies
- On static logics, dynamic logics, and complexity classes
- Languages that Capture Complexity Classes
- Complete Problems Involving Boolean Labelled Structures and Projection Transactions
- Probabilities on finite models
- Even Simple Programs Are Hard To Analyze
- Logical Description of Monotone NP Problems
- Logics with Zero-One Laws that Are Not Fragments of Bounded-Variable Infinitary Logic
- Existential least fixed-point logic and its relatives
- Relativized logspace and generalized quantifiers over finite ordered structures
- Generalized Quantifiers and Logical Reducibilities
- Hierarchies in classes of program schemes
- On Classes of Program Schemata
