Barsukov, Alexey; Madelaine, Florent R. On guarded extensions of MMSNP. (English) Zbl 07787582 Della Vedova, Gianluca (ed.) et al., Unity of logic and computation. 19th conference on computability in Europe, CiE 2023, Batumi, Georgia, July 24–28, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13967, 202-213 (2023). MSC: 03B70 68Qxx PDFBibTeX XMLCite \textit{A. Barsukov} and \textit{F. R. Madelaine}, Lect. Notes Comput. Sci. 13967, 202--213 (2023; Zbl 07787582) Full Text: DOI arXiv
Carvalho, Catarina; Madelaine, Florent; Martin, Barnaby; Zhuk, Dmitriy The complexity of quantified constraints: collapsibility, switchability, and the algebraic formulation. (English) Zbl 07650601 ACM Trans. Comput. Log. 24, No. 1, Paper No. 5, 26 p. (2023). MSC: 03B70 68-XX PDFBibTeX XMLCite \textit{C. Carvalho} et al., ACM Trans. Comput. Log. 24, No. 1, Paper No. 5, 26 p. (2023; Zbl 07650601) Full Text: DOI arXiv
Rosevear, Madelaine Gamble; Gayen, Bishakhdatta; Galton-Fenzi, Benjamin Keith The role of double-diffusive convection in basal melting of Antarctic ice shelves. (English) Zbl 1485.86015 Proc. Natl. Acad. Sci. USA 118, No. 6, Paper No. e2007541118, 9 p. (2021). MSC: 86A40 86-10 76F65 76R50 PDFBibTeX XMLCite \textit{M. G. Rosevear} et al., Proc. Natl. Acad. Sci. USA 118, No. 6, Paper No. e2007541118, 9 p. (2021; Zbl 1485.86015) Full Text: DOI
Bodirsky, Manuel; Madelaine, Florent; Mottet, Antoine A proof of the algebraic tractability conjecture for monotone monadic SNP. (English) Zbl 07393743 SIAM J. Comput. 50, No. 4, 1359-1409 (2021). MSC: 03B70 68Q19 PDFBibTeX XMLCite \textit{M. Bodirsky} et al., SIAM J. Comput. 50, No. 4, 1359--1409 (2021; Zbl 07393743) Full Text: DOI
Beaudou, Laurent; Foucaud, Florent; Madelaine, Florent; Nourine, Lhouari; Richard, Gaétan Complexity of conjunctive regular path query homomorphisms. (English) Zbl 1434.68139 Manea, Florin (ed.) et al., Computing with foresight and industry. 15th conference on computability in Europe, CiE 2019, Durham, UK, July 15–19, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11558, 108-119 (2019). MSC: 68P15 68Q25 68R10 PDFBibTeX XMLCite \textit{L. Beaudou} et al., Lect. Notes Comput. Sci. 11558, 108--119 (2019; Zbl 1434.68139) Full Text: DOI
Madelaine, Florent R.; Martin, Barnaby Consistency for counting quantifiers. (English) Zbl 1510.68031 Potapov, Igor (ed.) et al., 43rd international symposium on mathematical foundations of computer science. MFCS 2018, Liverpool, United Kingdom, August 27–31, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 117, Article 11, 13 p. (2018). MSC: 68Q25 03B70 08A70 PDFBibTeX XMLCite \textit{F. R. Madelaine} and \textit{B. Martin}, LIPIcs -- Leibniz Int. Proc. Inform. 117, Article 11, 13 p. (2018; Zbl 1510.68031) Full Text: DOI
Bodirsky, Manuel; Madelaine, Florent; Mottet, Antoine A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP. (English) Zbl 1452.03084 Proceedings of the 2018 33rd annual ACM/IEEE symposium on logic in computer science, LICS 2018, Oxford, UK, July 9–12, 2018. New York, NY: Association for Computing Machinery (ACM). 105-114 (2018). MSC: 03C13 03C05 03B16 68Q25 PDFBibTeX XMLCite \textit{M. Bodirsky} et al., in: Proceedings of the 2018 33rd annual ACM/IEEE symposium on logic in computer science, LICS 2018, Oxford, UK, July 9--12, 2018. New York, NY: Association for Computing Machinery (ACM). 105--114 (2018; Zbl 1452.03084) Full Text: DOI arXiv
Madelaine, Florent R.; Martin, Barnaby D. On the complexity of the model checking problem. (English) Zbl 1393.68078 SIAM J. Comput. 47, No. 3, 769-797 (2018). MSC: 68Q25 03B70 06A15 08A70 68Q60 PDFBibTeX XMLCite \textit{F. R. Madelaine} and \textit{B. D. Martin}, SIAM J. Comput. 47, No. 3, 769--797 (2018; Zbl 1393.68078) Full Text: DOI arXiv Link
Carvalho, Catarina; Madelaine, Florent; Martin, Barnaby From complexity to algebra and back: digraph classes, collapsibility, and the PGP. (English) Zbl 1401.68115 Proceedings of the 2015 30th annual ACM/IEEE symposium on logic in computer science, LICS 2015, Kyoto, Japan, July 6–10, 2015. Los Alamitos, CA: IEEE Computer Society (ISBN 978-1-4799-8875-4). 462-474 (2015). MSC: 68Q25 05C20 08A40 08A70 68Q17 PDFBibTeX XMLCite \textit{C. Carvalho} et al., in: Proceedings of the 2015 30th annual ACM/IEEE symposium on logic in computer science, LICS 2015, Kyoto, Japan, July 6--10, 2015. Los Alamitos, CA: IEEE Computer Society. 462--474 (2015; Zbl 1401.68115) Full Text: DOI arXiv
Chen, Hubie; Madelaine, Florent R.; Martin, Barnaby Quantified constraints and containment problems. (English) Zbl 1448.68248 Log. Methods Comput. Sci. 11, No. 3, Paper No. 9, 28 p. (2015). MSC: 68Q25 03B25 03B70 03C13 PDFBibTeX XMLCite \textit{H. Chen} et al., Log. Methods Comput. Sci. 11, No. 3, Paper No. 9, 28 p. (2015; Zbl 1448.68248) Full Text: DOI arXiv
Martin, Barnaby; Madelaine, Florent; Stacho, Juraj Constraint satisfaction with counting quantifiers. (English) Zbl 1392.68206 SIAM J. Discrete Math. 29, No. 2, 1065-1113 (2015). MSC: 68Q25 68Q17 68R10 PDFBibTeX XMLCite \textit{B. Martin} et al., SIAM J. Discrete Math. 29, No. 2, 1065--1113 (2015; Zbl 1392.68206) Full Text: DOI Link
Madelaine, Florent; Martin, Barnaby QCSP on partially reflexive cycles – the wavy line of tractability. (English) Zbl 1381.68099 Bulatov, Andrei A. (ed.) et al., Computer science – theory and applications. 8th international computer science symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25–29, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38535-3/pbk). Lecture Notes in Computer Science 7913, 322-333 (2013). MSC: 68Q25 PDFBibTeX XMLCite \textit{F. Madelaine} and \textit{B. Martin}, Lect. Notes Comput. Sci. 7913, 322--333 (2013; Zbl 1381.68099) Full Text: DOI arXiv
Madelaine, Florent; Martin, Barnaby The complexity of positive first-order logic without equality. (English) Zbl 1351.68119 ACM Trans. Comput. Log. 13, No. 1, Article No. 5, 17 p. (2012). MSC: 68Q25 03B20 PDFBibTeX XMLCite \textit{F. Madelaine} and \textit{B. Martin}, ACM Trans. Comput. Log. 13, No. 1, Article No. 5, 17 p. (2012; Zbl 1351.68119) Full Text: DOI arXiv
Madelaine, Florent; Martin, Barnaby; Stacho, Juraj Constraint satisfaction with counting quantifiers. (English) Zbl 1360.68514 Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. 7th international computer science symposium in Russia, CSR 2012, Nizhny Novgorod, Russia, July 3–7, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-30641-9/pbk). Lecture Notes in Computer Science 7353, 253-265 (2012). MSC: 68Q25 68Q17 68R10 PDFBibTeX XMLCite \textit{F. Madelaine} et al., Lect. Notes Comput. Sci. 7353, 253--265 (2012; Zbl 1360.68514) Full Text: DOI arXiv Link
de Boer, Frank S. (ed.); Bonsangue, Marcello M. (ed.); Madelaine, Eric (ed.) Formal methods for components and objects. 7th international symposium, FMCO 2008, Sophia Antipolis, France, October 21–23, 2008. Revised lectures. (English) Zbl 1173.68016 Lecture Notes in Computer Science 5751. Berlin: Springer (ISBN 978-3-642-04166-2/pbk). x, 299 p. (2009). MSC: 68-06 68N30 00B25 PDFBibTeX XMLCite \textit{F. S. de Boer} (ed.) et al., Formal methods for components and objects. 7th international symposium, FMCO 2008, Sophia Antipolis, France, October 21--23, 2008. Revised lectures. Berlin: Springer (2009; Zbl 1173.68016) Full Text: DOI
Madelaine, Florent R. Universal structures and the logic of forbidden patterns. (English) Zbl 1163.68019 Log. Methods Comput. Sci. 5, No. 2, Paper 13, 25 p. (2009). MSC: 68Q25 03B70 03C13 PDFBibTeX XMLCite \textit{F. R. Madelaine}, Log. Methods Comput. Sci. 5, No. 2, Paper 13, 25 p. (2009; Zbl 1163.68019) Full Text: DOI
Madelaine, Florent R.; Stewart, Iain A. Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies. (English) Zbl 1154.05055 Discrete Math. 308, No. 18, 4144-4164 (2008). MSC: 05C85 05C35 68R10 90C35 PDFBibTeX XMLCite \textit{F. R. Madelaine} and \textit{I. A. Stewart}, Discrete Math. 308, No. 18, 4144--4164 (2008; Zbl 1154.05055) Full Text: DOI
Madelaine, Florent; Stewart, Iain A. Constraint satisfaction, logic and forbidden patterns. (English) Zbl 1142.68035 SIAM J. Comput. 37, No. 1, 132-163 (2007). MSC: 68Q19 03C13 68Q15 PDFBibTeX XMLCite \textit{F. Madelaine} and \textit{I. A. Stewart}, SIAM J. Comput. 37, No. 1, 132--163 (2007; Zbl 1142.68035) Full Text: DOI Link
Martin, Barnaby; Madelaine, Florent Hierarchies in fragments of monadic strict NP. (English) Zbl 1150.03315 Cooper, S. Barry (ed.) et al., Computation and logic in the real world. Third conference on computability in Europe, CiE 2007, Siena, Italy, June 18–23, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73000-2/pbk). Lecture Notes in Computer Science 4497, 542-550 (2007). MSC: 03D05 03B15 05C15 PDFBibTeX XMLCite \textit{B. Martin} and \textit{F. Madelaine}, Lect. Notes Comput. Sci. 4497, 542--550 (2007; Zbl 1150.03315) Full Text: DOI
Madelaine, Florent Universal structures and the logic of forbidden patterns. (English) Zbl 1225.68094 Ésik, Zoltán (ed.), Computer science logic. 20th international workshop, CSL 2006, 15th annual conference of the EACSL, Szeged, Hungary, September 25–29, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-45458-8/pbk). Lecture Notes in Computer Science 4207, 471-485 (2006). MSC: 68Q19 03C13 PDFBibTeX XMLCite \textit{F. Madelaine}, Lect. Notes Comput. Sci. 4207, 471--485 (2006; Zbl 1225.68094) Full Text: DOI arXiv
Dantchev, Stefan; Madelaine, Florent Bounded-degree forbidden patterns problems are constraint satisfaction problems. (English) Zbl 1185.68640 Grigoriev, Dima (ed.) et al., Computer science – theory and applications. First international computer science symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8–12, 2006. Proceedings. Berlin: Springer (ISBN 3-540-34166-8/pbk). Lecture Notes in Computer Science 3967, 159-170 (2006). MSC: 68T20 03B70 68Q25 PDFBibTeX XMLCite \textit{S. Dantchev} and \textit{F. Madelaine}, Lect. Notes Comput. Sci. 3967, 159--170 (2006; Zbl 1185.68640) Full Text: DOI
Martin, Barnaby; Madelaine, Florent Towards a trichotomy for quantified \(H\)-coloring. (English) Zbl 1145.68436 Beckmann, Arnold (ed.) et al., Logical approaches to computational barriers. Second conference on computability in Europe, CiE 2006, Swansea, UK, June 30–July 5, 2006. Proceedings. Berlin: Springer (ISBN 3-540-35466-2/pbk). Lecture Notes in Computer Science 3988, 342-352 (2006). MSC: 68Q25 05C15 68R10 91A43 PDFBibTeX XMLCite \textit{B. Martin} and \textit{F. Madelaine}, Lect. Notes Comput. Sci. 3988, 342--352 (2006; Zbl 1145.68436) Full Text: DOI
Feder, Tomás; Madelaine, Florent; Stewart, Iain A. Dichotomies for classes of homomorphism problems involving unary functions. (English) Zbl 1070.68133 Theor. Comput. Sci. 314, No. 1-2, 1-43 (2004). MSC: 68T20 PDFBibTeX XMLCite \textit{T. Feder} et al., Theor. Comput. Sci. 314, No. 1--2, 1--43 (2004; Zbl 1070.68133) Full Text: DOI Link
Madelaine, Florent R.; Stewart, Iain A. Some problems not definable using structure homomorphisms. (English) Zbl 1101.68038 Ars Comb. 67, 153-159 (2003). MSC: 68Q19 03C13 05C85 PDFBibTeX XMLCite \textit{F. R. Madelaine} and \textit{I. A. Stewart}, Ars Comb. 67, 153--159 (2003; Zbl 1101.68038)