{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:48:00Z","timestamp":1770994080137,"version":"3.50.1"},"reference-count":45,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2018,4,19]],"date-time":"2018-04-19T00:00:00Z","timestamp":1524096000000},"content-version":"unspecified","delay-in-days":7809,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[1996,12]]},"abstract":"<jats:p>It is well known that every algorithmic problem definable by a formula of first-order logic can be solved in polynomial time, since all these problems are in<jats:bold>L<\/jats:bold>(see Aho and Ullman (1979) and Immerman (1987)). Using an old technique of Hanf (Hanf 1965) and other techniques developed to prove the decidability of formal theories in mathematical logic, it is shown that an arbitrary<jats:bold>FO<\/jats:bold>-problem over relational structures of bounded degree can be solved in linear time.<\/jats:p>","DOI":"10.1017\/s0960129500070079","type":"journal-article","created":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T19:42:44Z","timestamp":1557690164000},"page":"505-526","source":"Crossref","is-referenced-by-count":89,"title":["Linear time computable problems and first-order descriptions"],"prefix":"10.1017","volume":"6","author":[{"given":"Detlef","family":"Seese","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,4,19]]},"reference":[{"key":"S0960129500070079_ref044","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54233-7_154"},{"key":"S0960129500070079_ref043","first-page":"242","volume-title":"Proceedings of CSL'94","volume":"933","author":"Stolboushkin","year":"1994"},{"key":"S0960129500070079_ref040","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19870330107"},{"key":"S0960129500070079_ref007","first-page":"235","volume-title":"Model-Theoretic Logics","author":"Baudisch","year":"1982"},{"key":"S0960129500070079_ref026","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0099486"},{"key":"S0960129500070079_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90064-Z"},{"key":"S0960129500070079_ref036","volume-title":"Computational Complexity","author":"Papadimitriou","year":"1994"},{"key":"S0960129500070079_ref012","volume-title":"Introduction to Algorithms","author":"Cormen","year":"1990"},{"key":"S0960129500070079_ref042","first-page":"83","volume-title":"Tree Automata and Languages","author":"Seese","year":"1992"},{"key":"S0960129500070079_ref034","volume-title":"Graph Algorithms and NP-Completeness","author":"Mehlhorn","year":"1984"},{"key":"S0960129500070079_ref032","doi-asserted-by":"publisher","DOI":"10.1137\/0216051"},{"key":"S0960129500070079_ref041","unstructured":"Schwentick T. (1994) Graph connectivity and monadic NP, Informatik-Bericht Nr. 2\/94, Johannes Gutenberg - Universit\u00e4t Mainz, Institut f\u00fcr Informatik, FB 17 1-33."},{"key":"S0960129500070079_ref031","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80029-8"},{"key":"S0960129500070079_ref028","first-page":"132","volume-title":"The Theory of Models","author":"Hanf","year":"1965"},{"key":"S0960129500070079_ref033","unstructured":"Maltsev A. I. (1959) Regular products of models, Izv. Acad. Nauk. SSSR, Ser. Mat., 23 489-502."},{"key":"S0960129500070079_ref010","doi-asserted-by":"publisher","DOI":"10.2307\/2267689"},{"key":"S0960129500070079_ref030","article-title":"Upper and Lower Bounds for First Order Expressability","volume":"25","author":"Immerman","year":"1982","journal-title":"JCSS"},{"key":"S0960129500070079_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457985"},{"key":"S0960129500070079_ref009","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90032-X"},{"key":"S0960129500070079_ref001","unstructured":"Abitoul S. , Vardi M. and Vianu V. (1992) Fixpoint logics, relational machines and computational complexity, Proceedings of the 33rd Annual Symposium on Foundations of Computer Science 156-192."},{"key":"S0960129500070079_ref005","doi-asserted-by":"publisher","DOI":"10.1145\/174147.169807"},{"key":"S0960129500070079_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"S0960129500070079_ref003","doi-asserted-by":"crossref","unstructured":"Aho A. and Ullman J. D. (1979) Universality of Data Retrieval Languages, 6th Symposium on Principles of Programming Languages 110-117.","DOI":"10.1145\/567752.567763"},{"key":"S0960129500070079_ref016","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-13331-3_51"},{"key":"S0960129500070079_ref039","first-page":"153","volume-title":"Surveys in Combinatorics","author":"Robertson","year":"1985"},{"key":"S0960129500070079_ref002","volume-title":"The design and analysis of computer algorithms","author":"Aho","year":"1974"},{"key":"S0960129500070079_ref029","doi-asserted-by":"publisher","DOI":"10.1007\/BF02944970"},{"key":"S0960129500070079_ref027","first-page":"479","volume-title":"Model- Theoretic Logics","author":"Gurevich","year":"1985"},{"key":"S0960129500070079_ref019","first-page":"27","volume-title":"Complexity of Computation","volume":"7","author":"Fagin","year":"1974"},{"key":"S0960129500070079_ref011","unstructured":"Compton K. and Henson C. (1987) A uniform method for proving lower bounds on the computational complexity of logical theories, The University of Michigan, Computing Research Laboratory, CRL-TR-04-87."},{"key":"S0960129500070079_ref017","unstructured":"Eaves B. and Rothblum U. (1994) Linear Problems and linear algorithms, Rutcor Research Report, RRR28-94."},{"key":"S0960129500070079_ref013","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90268-2"},{"key":"S0960129500070079_ref015","first-page":"115","volume-title":"Computer Science Logic 1992, San Miniato","volume":"702","author":"Creignou","year":"1993"},{"key":"S0960129500070079_ref020","first-page":"78","article-title":"On monadic NP vs. monadic co-NR","volume":"120","author":"Fagin","year":"1993","journal-title":"The Proceedings of the 8th Annual IEEE Conference on Structure in Complexity Theory 19-30"},{"key":"S0960129500070079_ref018","volume-title":"Mathematical Logic","author":"Ebbinghaus","year":"1993"},{"key":"S0960129500070079_ref022","volume-title":"Proceedings 4th Twente workshop on graphs and combinatorial optimization","volume":"110","author":"Giakoumakis","year":"1995"},{"key":"S0960129500070079_ref023","doi-asserted-by":"crossref","unstructured":"Giammarresi D. , Restivo A. , Seibert S. and Thomas W. (1993) Monadic second order-logic over rectangular pictures and recognizability by tiling systems, Report No. 9318, Christian-Albrechts-Universit\u00e4t Kiel (also to appear in Information and Computation).","DOI":"10.1007\/3-540-57785-8_155"},{"key":"S0960129500070079_ref035","volume-title":"Computation: Finite and Infinite Machines","author":"Minsky","year":"1967"},{"key":"S0960129500070079_ref024","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054190000217"},{"key":"S0960129500070079_ref004","doi-asserted-by":"publisher","DOI":"10.2307\/2274958"},{"key":"S0960129500070079_ref037","first-page":"58","volume-title":"Logic, Methodology and Philosophy of Science","volume":"II","author":"Rabin","year":"1965"},{"key":"S0960129500070079_ref025","first-page":"248","volume-title":"Proceedings Computer Science Logic 1992, San Miniato","volume":"702","author":"Grandjaen","year":"1993"},{"key":"S0960129500070079_ref038","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71116-9"},{"key":"S0960129500070079_ref021","first-page":"105","volume-title":"Logic Colloquium \u201981","author":"Gaifman","year":"1982"},{"key":"S0960129500070079_ref045","volume-title":"Computational Complexity","author":"Wagner","year":"1986"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129500070079","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,12]],"date-time":"2020-12-12T13:00:18Z","timestamp":1607778018000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129500070079\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,12]]},"references-count":45,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1996,12]]}},"alternative-id":["S0960129500070079"],"URL":"https:\/\/doi.org\/10.1017\/s0960129500070079","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,12]]}}}