| Publication | Date of Publication | Type |
|---|
| Descriptive complexity for minimal time of cellular automata | 2024-12-19 | Paper |
| Conjunctive grammars, cellular automata and logic | 2024-08-13 | Paper |
Inductive definitions in logic versus programs of real-time cellular automata
Theoretical Computer Science | 2024-03-01 | Paper |
| Definability by Horn formulas and linear time on cellular automata | 2020-05-27 | Paper |
First-order queries on structures of bounded degree are computable with constant delay
ACM Transactions on Computational Logic | 2017-07-12 | Paper |
A logical approach to locality in pictures languages
Journal of Computer and System Sciences | 2016-06-13 | Paper |
Descriptive complexity for pictures languages
(available as arXiv preprint) | 2012-11-22 | Paper |
On Acyclic Conjunctive Queries and Constant Delay Enumeration
Computer Science Logic | 2009-03-05 | Paper |
Computing the<i>j</i>th solution of a first-order query
RAIRO - Theoretical Informatics and Applications | 2008-07-21 | Paper |
STACS 2004
Lecture Notes in Computer Science | 2007-10-01 | Paper |
Graph properties checkable in linear time in the number of vertices
Journal of Computer and System Sciences | 2004-08-10 | Paper |
| scientific article; zbMATH DE number 2079027 (Why is no real title available?) | 2004-07-21 | Paper |
| scientific article; zbMATH DE number 1948176 (Why is no real title available?) | 2003-07-10 | Paper |
Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time
SIAM Journal on Computing | 2003-01-05 | Paper |
Monadic logical definability of nondeterministic linear time
Computational Complexity | 1999-05-24 | Paper |
SAT-Problems and Reductions with Respect to the Number of Variables
Journal Of Logic And Computation | 1997-08-28 | Paper |
Sorting, linear time and the satisfiability problem
Annals of Mathematics and Artificial Intelligence | 1996-12-01 | Paper |
Linear Time Algorithms and NP-Complete Problems
SIAM Journal on Computing | 1994-08-14 | Paper |
Invariance properties of RAMs and linear time
Computational Complexity | 1994-07-13 | Paper |
| scientific article; zbMATH DE number 512978 (Why is no real title available?) | 1994-06-13 | Paper |
| scientific article; zbMATH DE number 515738 (Why is no real title available?) | 1994-06-02 | Paper |
First-order spectra with one variable
Journal of Computer and System Sciences | 1990-01-01 | Paper |
A Nontrivial Lower Bound for an NP Problem on Automata
SIAM Journal on Computing | 1990-01-01 | Paper |
A Natural NP-Complete Problem with a Nontrivial Lower Bound
SIAM Journal on Computing | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4019038 (Why is no real title available?) | 1987-01-01 | Paper |
Universal quantifiers and time complexity of random access machines
Mathematical Systems Theory | 1985-01-01 | Paper |
| scientific article; zbMATH DE number 3873306 (Why is no real title available?) | 1984-01-01 | Paper |
The Spectra of First-Order Sentences and Computational Complexity
SIAM Journal on Computing | 1984-01-01 | Paper |
Complexity of the first-order theory of almost all finite structures
Information and Control | 1983-01-01 | Paper |
| scientific article; zbMATH DE number 3510280 (Why is no real title available?) | 1976-01-01 | Paper |
| scientific article; zbMATH DE number 3531369 (Why is no real title available?) | 1976-01-01 | Paper |
