{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:12:36Z","timestamp":1761610356611,"version":"build-2065373602"},"reference-count":46,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2013,7,29]],"date-time":"2013-07-29T00:00:00Z","timestamp":1375056000000},"content-version":"vor","delay-in-days":6784,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Electronic Notes in Theoretical Computer Science"],"published-print":{"date-parts":[[1995]]},"DOI":"10.1016\/s1571-0661(05)80203-8","type":"journal-article","created":{"date-parts":[[2005,5,25]],"date-time":"2005-05-25T08:37:08Z","timestamp":1117010228000},"page":"246-259","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":5,"special_numbering":"C","title":["Linear Time Computable Problems and Logical Descriptions"],"prefix":"10.1016","volume":"2","author":[{"given":"Detlef","family":"Seese","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S1571-0661(05)80203-8_BIB1","first-page":"156","article-title":"Fixpoint logics, relational machines, and computational complexity","author":"Abitoul","year":"1992","journal-title":"IEEE FOCS"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB2","doi-asserted-by":"crossref","unstructured":"S. Arnborg, B. Courcelle, A. Proskurowski and D. Seese, An algebraic theory of graph reduction, Technical Report LaBRI-90\u201302, Universite de Bordeaux. Jan. 1990, JACM, vol. 40 No. 5, 1993 pp. 1134\u20131164. (Extended abstract in Lee. Notes Comp. Sci. 532, 1991, pp. 70\u201383.)","DOI":"10.1145\/174147.169807"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB3","series-title":"Addison Wesley","article-title":"The design and analysis of computer algorithms","author":"Aho","year":"1974"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB4","first-page":"110","article-title":"Universality of Data Retrieval Languages","author":"Aho","year":"1979","journal-title":"6th Symposium on Principles of Programming Languages"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB5","doi-asserted-by":"crossref","first-page":"113","DOI":"10.2307\/2274958","article-title":"Reachability is harder for directed than for undirected finite graphs","author":"Ajtai","year":"1990","journal-title":"Journal of Symbolic Logic, 55 (1)"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB6","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","article-title":"Easy problems for tree-decomposable graphs","author":"Arnborg","year":"1991","journal-title":"Journal of Algorithms 12"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB7","first-page":"235","article-title":"Decidability and Quantifier-Elimination, in Model-Theoretic Logics","author":"Baudisch","year":"1982"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB8","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0196-6774(87)90039-3","article-title":"Linear time computation of optimal subgraphs of decomposable graphs","author":"Bern","year":"1987","journal-title":"J. Algorithms 8"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB9","series-title":"MIT\/LCS\/TR-394, MIT","article-title":"Dynamic programming on graphs with bounded tree-width","author":"Bodlaender","year":"1987"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB10","series-title":"Vieweg","article-title":"Berechenbarkeit Komplexit\u00e4t Logik","author":"B\u00f6rger","year":"1992"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB11","series-title":"manuscript, July 21","article-title":"Automatic generation of linear algorithms from predicate calculus descriptions of problems on recursively constructed graph families","author":"Borie","year":"1988"},{"year":"1990","series-title":"Introduction to Algorithms","author":"Cormen","key":"10.1016\/S1571-0661(05)80203-8_BIB12"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB13","series-title":"Report 1\u20138852, Bordeaux-1 University","article-title":"The monadic second order logic of graphs. III. Tree-width, Forbidden Minors, and Complexity Issues","author":"Courcelle","year":"1988"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB14","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","article-title":"Recognizability and second-order definability for sets of finite graphs","author":"Courcelle","year":"1990","journal-title":"Information and Comput. 85"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB15","doi-asserted-by":"crossref","unstructured":"B. Courcelle, Monadic second-order logic and hypergraph orientation, In Proceedings Eighth annual IEEE Symposium on Logic in Computer Science, June 19\u201323, 1993, Montreal, Canada, pp. 179\u2013190.","DOI":"10.1109\/LICS.1993.287589"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB16","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0304-3975(93)90064-Z","article-title":"Monadic second-order evaluations on tree-decomposable graphs","author":"Courcelle","year":"1993","journal-title":"Theoretical Computer Science 109"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB17","first-page":"52","article-title":"Logical reductibility and monadic","author":"Cosmadakis","year":"1993","journal-title":"NP, IEEE"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB18","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/3-540-56992-8_9","article-title":"The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving","author":"Creignou","year":"1993","journal-title":"NP -completeness, Lecture Notes in Computer Science CSL'92, San Miniato"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB19","first-page":"36","author":"Downey","year":"1992","journal-title":"Fixed-Parameter Intractability (Extended Abstract)"},{"year":"1993","series-title":"Mathematical Logic","author":"Ebbinghaus","key":"10.1016\/S1571-0661(05)80203-8_BIB20"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB21","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4064\/fm-49-2-129-141","article-title":"An application of games to the completeness problem for formalized theories","author":"Ehrenfeucht","year":"1961","journal-title":"Fund. Math., 49"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB22","unstructured":"R. Fagin, Generalized First-Order spectra and polynomial-time recognizable sets, In Complexity of Computation, (ed. R. Karp) SIAM-AMS Proc. 7, 1974, pp. 27\u201341"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB23","doi-asserted-by":"crossref","unstructured":"R. Fagin, L. Stockmeyer, and M. Vardi, On monadic NP es. monadic co-NP, In The Proceedings of the 8th Annual IEEE Conference on Structure in Complexity Theory, 1993, pp. 19\u201330.","DOI":"10.1109\/SCT.1993.336544"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB24","first-page":"35","article-title":"Sur quelques classifications des syst\u00e8mes de relations","author":"Fra\u00efss\u00e9","year":"1954","journal-title":"Publ. Sci. Univ. Alger. Sr. A, 1"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB25","series-title":"Logic Colloquium'81, North-Holland","first-page":"105","article-title":"On local and nonlocal properties","author":"Gaifman","year":"1982"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB26","doi-asserted-by":"crossref","unstructured":"E. Gr\u00e4del, On the notion of linear time computability, Proc. 3rd Italian Conf. Theoret. Comput. Sci. 1989, World Scientific Publ. Co. pp. 323\u2013334, also appear in Internat. J. Foundations Comput. Sci. 1, 1990 pp. 295\u2013307.","DOI":"10.1142\/S0129054190000217"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB27","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1007\/3-540-56992-8_16","article-title":"Linear time algorithms and","author":"Grandjaen","year":"1993","journal-title":"NP -complete problems, Lecture Notes in Computer Science CSL'92, San Miniato"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB28","unstructured":"Y. Gurevich, Logic and the challenge of computer science, Univ. Michigan Tech. Report CRL-TR\u201310\u201385, Sept. 1985."},{"key":"10.1016\/S1571-0661(05)80203-8_BIB29","doi-asserted-by":"crossref","unstructured":"Y. Gurevich, and S. Shelah, Nearly linear time, Springer Lecture Notes in Computer Science 363, pp. 108\u2013118. 86.","DOI":"10.1007\/3-540-51237-3_10"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB30","series-title":"The Theory of Models","first-page":"132","article-title":"Model-theoretic methods in the study of elementary logic","author":"Hanf","year":"1965"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB31","series-title":"Preprint","article-title":"A framework to design algorithms for optimization problems on graphs","author":"Hohberg","year":"1990"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB32","series-title":"JCSS, Vol. 25, No. 1","article-title":"Upper and Lower Bounds for First Order Expressibility","author":"Immerman","year":"1982"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB33","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","article-title":"Relational queries computable in polynomial time","author":"Immerman","year":"1986","journal-title":"Information and Control 68"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB34","doi-asserted-by":"crossref","unstructured":"N. Immerman, Languages that capture complexity classes, SIAM J. Comput., Vol. 16, No. 4, August 1987, pp. 760\u2013778. A preliminary version of this paper appeared in the 15th ACM STOC Symp., 1983, 347\u2013354.","DOI":"10.1137\/0216051"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB35","doi-asserted-by":"crossref","unstructured":"N. Immerman, Descriptive and computational complexity, Computational Complexity Theory, Proc. Symp. Applied Math. Vol. 38 (J. Hartmanis, ed.), 1989, pp. 75\u201391.","DOI":"10.1090\/psapm\/038\/1020810"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB36","first-page":"327","article-title":"Logical definability of NP-optimisation problems with monadic auxiliary predicates","author":"Lautemann","year":"1990","journal-title":"preprint"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB37","series-title":"Addison-Wesley Publishing Company, Reading, Massachusetts","article-title":"Computational Complexity","author":"Papadimitriou","year":"1994"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB38","unstructured":"N. Robertson, and P. D. Seymour, Graph minors XIII; The disjoint path problem, Journal of Combinatorial Theory (to appear)."},{"key":"10.1016\/S1571-0661(05)80203-8_BIB39","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1002\/malq.19870330107","article-title":"Second-order and inductive definability on finite structures","author":"de Rougemont","year":"1987","journal-title":"Zeitschrift f. math. Logik und Grundlagen d. Math., Bd. 33"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB40","series-title":"Dissertation (A), AdW d. DDR, Berlin","article-title":"Die Baumweite von Graphen als ein Mass fuer die Kompliziertheit algorithmischer Probleme","author":"Schemer","year":"1989"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB41","first-page":"1","article-title":"Graph connectivity and monadic NP","author":"Schwentick","year":"1994","journal-title":"Informatik-Bericht Nr. 2\/94, Johannes Gutenberg - Universit\u00e4t Mainz, Institut f\u00fcr Informatik, FB 17, 24"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB42","doi-asserted-by":"crossref","unstructured":"D. Seese, Tree-partite graphs and the complexity of algorithms, Preprint P-MATH-08\/86, Karl-Weierstrass-Institute for Mathematics, Academic of Sciences, Berlin 1986, an extended abstract appeared also in FCT'85, edited by L. Budach, Lecture Notes in Computer Science 199, 1985, pp. 412\u2013421.","DOI":"10.1007\/BFb0028825"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB43","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0168-0072(91)90054-P","article-title":"The structure of the models of decidable monadic theories of graphs","author":"Seese","year":"1991","journal-title":"Annals of Pure and Applied Logic 53"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB44","series-title":"in Tree Automata and Languages","first-page":"83","article-title":"Interpretability and tree automata: a simple way to solve algorithmic problems on graphs closely related to trees","author":"Seese","year":"1992"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB45","first-page":"1","article-title":"FO-Problems and Linear Time Computability","author":"Seese","year":"1995","journal-title":"Bericht 315, AIFB Institut fuer Angewandte Informatik und Formale Beschreibungsverfahren, Universit\u00e4t Karlsruhe (TH)"},{"key":"10.1016\/S1571-0661(05)80203-8_BIB46","doi-asserted-by":"crossref","unstructured":"W. Thomas, On logics, tilings, and automata, In Proc. 18th ICALP, Lecture Notes in Computer Science 510, Springer Verlag, 1991, pp. 441\u2013454.","DOI":"10.1007\/3-540-54233-7_154"}],"container-title":["Electronic Notes in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571066105802038?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571066105802038?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:08:00Z","timestamp":1761610080000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1571066105802038"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"references-count":46,"alternative-id":["S1571066105802038"],"URL":"https:\/\/doi.org\/10.1016\/s1571-0661(05)80203-8","relation":{},"ISSN":["1571-0661"],"issn-type":[{"type":"print","value":"1571-0661"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Linear Time Computable Problems and Logical Descriptions","name":"articletitle","label":"Article Title"},{"value":"Electronic Notes in Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/S1571-0661(05)80203-8","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 1995 Elsevier B.V.","name":"copyright","label":"Copyright"}]}}