{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:45:24Z","timestamp":1725551124491},"publisher-location":"Berlin, Heidelberg","reference-count":46,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540006237"},{"type":"electronic","value":"9783540364948"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-36494-3_34","type":"book-chapter","created":{"date-parts":[[2010,3,29]],"date-time":"2010-03-29T21:12:04Z","timestamp":1269897124000},"page":"379-390","source":"Crossref","is-referenced-by-count":3,"title":["Solving Order Constraints in Logarithmic Space"],"prefix":"10.1007","author":[{"given":"Andrei","family":"Krokhin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benoit","family":"Larose","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,2,17]]},"reference":[{"issue":"2","key":"34_CR1","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/PL00001603","volume":"9","author":"M. Alvarez","year":"2000","unstructured":"M. Alvarez and R. Greenlaw. A compendium of problems complete for symmetric logarithmic space. Computational Complexity, 9(2):123\u2013145, 2000.","journal-title":"Computational Complexity"},{"key":"34_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(98)00134-0","volume":"212","author":"M. Benke","year":"1999","unstructured":"M. Benke. Some complexity bounds for subtype inequalities. Theoretical Computer Science, 212:3\u201327, 1999.","journal-title":"Theoretical Computer Science"},{"key":"34_CR3","doi-asserted-by":"crossref","unstructured":"A.A. Bulatov. A dichotomy theorem for constraints on a three-element set. In Proceedings 43rd IEEE Symposium on Foundations of Computer Science, FOCS\u201902, pages 649\u2013658, 2002.","DOI":"10.1109\/SFCS.2002.1181990"},{"key":"34_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1007\/3-540-45022-X_24","volume-title":"Constraint satisfaction problems and finite algebras","author":"A.A. Bulatov","year":"2000","unstructured":"A.A. Bulatov, A.A. Krokhin, and P.G. Jeavons. Constraint satisfaction problems and finite algebras. In Proceedings 27th International Colloquium on Automata, Languages and Programming, ICALP\u201900, volume 1853 of Lecture Notes in Computer Science, pages 272\u2013282. Springer-Verlag, 2000."},{"key":"34_CR5","doi-asserted-by":"crossref","unstructured":"A.A. Bulatov, A.A. Krokhin, and P.G. Jeavons. The complexity of maximal constraint languages. In Proceedings 33rd ACM Symposium on Theory of Computing, STOC\u201901, pages 667\u2013674, 2001.","DOI":"10.1145\/380752.380868"},{"key":"34_CR6","first-page":"199","volume":"311","author":"E. Corominas","year":"1990","unstructured":"E. Corominas. Sur les ensembles ordonn\u00e9s projectif et la propri\u00e9tr\u00e9 du point fixe. C. R. Acad. Sci. Paris Serie I Math., 311:199\u2013204, 1990.","journal-title":"C. R. Acad. Sci. Paris Serie I Math."},{"key":"34_CR7","doi-asserted-by":"crossref","unstructured":"N. Creignou, S. Khanna, and M. Sudan. Complexity Classifications of Boolean Constraint Satisfaction Problems, volume 7 of SIAM Monographs on Discrete Mathematics and Applications. 2001.","DOI":"10.1137\/1.9780898718546"},{"key":"34_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1007\/3-540-45465-9_36","volume-title":"Constraint satisfaction problems in non-deterministic logarithmic space","author":"V. Dalmau","year":"2002","unstructured":"V. Dalmau. Constraint satisfaction problems in non-deterministic logarithmic space. In Proceedings 29th International Colloquium on Automata, Languages and Programming, ICALP\u201902, volume 2380 of Lecture Notes in Computer Science, pages 414\u2013425. Springer-Verlag, 2002."},{"key":"34_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/978-3-540-48085-3_12","volume-title":"Set functions and width 1 problems","author":"V. Dalmau","year":"1999","unstructured":"V. Dalmau and J. Pearson. Set functions and width 1 problems. In Proceedings 5th International Conference on Constraint Programming, CP\u201999, volume 1713 of Lecture Notes in Computer Science, pages 159\u2013173. Springer-Verlag, 1999."},{"key":"34_CR10","unstructured":"J. Demetrovics, L. Hann\u00e1k, and L. R\u00f3nyai. Near-unanimity functions of partial orders. In Proceedings 14th International Symposium on Multiple-Valued Logic, ISMVL\u201984, pages 52\u201356, 1984."},{"key":"34_CR11","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0012-365X(81)90201-6","volume":"35","author":"D. Duffus","year":"1981","unstructured":"D. Duffus and I. Rival. A structure theory for ordered sets. Discrete Mathematics, 35:53\u2013118, 1981.","journal-title":"Discrete Mathematics"},{"key":"34_CR12","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1998","unstructured":"T. Feder and M.Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal of Computing, 28:57\u2013104, 1998.","journal-title":"SIAM Journal of Computing"},{"key":"34_CR13","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0004-3702(00)00078-3","volume":"124","author":"G. Gottlob","year":"2000","unstructured":"G. Gottlob, L. Leone, and F. Scarcello. A comparison of structural CSP decomposition methods. Artificial Intelligence, 124:243\u2013282, 2000.","journal-title":"Artificial Intelligence"},{"issue":"3","key":"34_CR14","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1006\/jcss.2001.1809","volume":"64","author":"G. Gottlob","year":"2002","unstructured":"G. Gottlob, L. Leone, and F. Scarcello. Hypertree decomposition and tractable queries. Journal of Computer and System Sciences, 64(3):579\u2013627, 2002.","journal-title":"Journal of Computer and System Sciences"},{"key":"34_CR15","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(92)90149-A","volume":"101","author":"E. Gr\u00e4del","year":"1992","unstructured":"E. Gr\u00e4del. Capturing complexity classes by fragments of second-order logic. Theoretical Computer Science, 101:35\u201357, 1992.","journal-title":"Theoretical Computer Science"},{"key":"34_CR16","doi-asserted-by":"crossref","unstructured":"M. Grohe, T. Schwentick, and L. Segoufin. When is the evaluation of conjunctive queries tractable? In Proceedings 33rd ACM Symposium on Theory of Computing, STOC\u201901, pages 657\u2013666, 2001.","DOI":"10.1145\/380752.380867"},{"key":"34_CR17","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P. Hell","year":"1990","unstructured":"P. Hell and J. Ne\u0161et\u0159il. On the complexity of H-coloring. Journal of Combinatorial Theory, Ser.B, 48:92\u2013110, 1990.","journal-title":"Journal of Combinatorial Theory, Ser.B"},{"key":"34_CR18","doi-asserted-by":"crossref","unstructured":"M. Hoang and J.C. Mitchell. Lower bounds on type inference with subtypes. In Proceedings 22nd ACM Symposium on Principles of Programming Languages, POPL\u201995, pages 176\u2013185, 1995.","DOI":"10.1145\/199448.199481"},{"key":"34_CR19","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman. Nondeterministic space is closed under complementation. SIAM Journal on Computing, 17:935\u2013939, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"34_CR20","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","volume":"200","author":"P.G. Jeavons","year":"1998","unstructured":"P.G. Jeavons. On the algebraic structure of combinatorial problems. Theoretical Computer Science, 200:185\u2013204, 1998.","journal-title":"Theoretical Computer Science"},{"issue":"1\u20132","key":"34_CR21","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0004-3702(98)00022-8","volume":"101","author":"P.G. Jeavons","year":"1998","unstructured":"P.G. Jeavons, D.A. Cohen, and M.C. Cooper. Constraints, consistency and closure. Artificial Intelligence, 101(1\u20132):251\u2013265, 1998.","journal-title":"Artificial Intelligence"},{"key":"34_CR22","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1007\/3-540-60299-2_17","volume-title":"A unifying framework for tractable constraints","author":"P.G. Jeavons","year":"1995","unstructured":"P.G. Jeavons, D.A. Cohen, and M. Gyssens. A unifying framework for tractable constraints. In Proceedings 1st International Conference on Constraint Programming, CP\u201995, volume 976 of Lecture Notes in Computer Science, pages 276\u2013291. Springer-Verlag, 1995."},{"key":"34_CR23","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P.G. Jeavons","year":"1997","unstructured":"P.G. Jeavons, D.A. Cohen, and M. Gyssens. Closure properties of constraints. Journal of the ACM, 44:527\u2013548, 1997.","journal-title":"Journal of the ACM"},{"key":"34_CR24","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0004-3702(93)90063-H","volume":"64","author":"L. Kirousis","year":"1993","unstructured":"L. Kirousis. Fast parallel constraint satisfaction. Artificial Intelligence, 64:147\u2013160, 1993.","journal-title":"Artificial Intelligence"},{"key":"34_CR25","doi-asserted-by":"crossref","unstructured":"J. K\u00f6bler and J. Tor\u00e1n. The complexity of graph isomorphism for colored graphs with color classes of size 2 and 3. In Proceedings 19th Symposium on Theoretical Aspects of Computer Science, STACS\u201902, pages 121\u2013132, 2002.","DOI":"10.1007\/3-540-45841-7_9"},{"key":"34_CR26","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1006\/jcss.2000.1713","volume":"61","author":"Ph.G. Kolaitis","year":"2000","unstructured":"Ph.G. Kolaitis and M.Y. Vardi. Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Sciences, 61:302\u2013332, 2000.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"34_CR27","first-page":"32","volume":"13","author":"V. Kumar","year":"1992","unstructured":"V. Kumar. Algorithms for constraint satisfaction problems: A survey. AI Magazine, 13(1):32\u201344, 1992.","journal-title":"AI Magazine"},{"key":"34_CR28","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1023\/A:1010681409599","volume":"18","author":"G. Kun","year":"2001","unstructured":"G. Kun and Cs. Szab\u00f3. Order varieties and monotone retractions of finite posets. Order, 18:79\u201388, 2001.","journal-title":"Order"},{"key":"34_CR29","unstructured":"B. Larose and L. Z\u00e1dori. The complexity of the extendibility problem for finite posets. manuscript, obtainable from http:\/\/cicma.mathstat.concordia.ca\/faculty\/larose\/ ."},{"key":"34_CR30","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0012-365X(95)00312-K","volume":"163","author":"B. Larose","year":"1997","unstructured":"B. Larose and L. Z\u00e1dori. Algebraic properties and dismantlability of finite posets. Discrete Mathematics, 163:89\u201399, 1997.","journal-title":"Discrete Mathematics"},{"key":"34_CR31","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0304-3975(82)90058-5","volume":"19","author":"H. Lewis","year":"1982","unstructured":"H. Lewis and C. Papadimitriou. Symmetric space bounded computation. Theoretical Computer Science, 19:161\u2013188, 1982.","journal-title":"Theoretical Computer Science"},{"key":"34_CR32","doi-asserted-by":"crossref","unstructured":"K. Lodaya and P. Weil. Series-parallel posets: algebra, automata and languages. In Proceedings 15th Symposium on Theoretical Aspects of Computer Science, STACS\u201998, pages 555\u2013565, 1998.","DOI":"10.1007\/BFb0028590"},{"key":"34_CR33","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/978-94-009-2639-4_4","volume-title":"Algorithms and Order (Ottawa, 1987)","author":"R.H. M\u00f6hring","year":"1989","unstructured":"R.H. M\u00f6hring. Computationally tractable classes of ordered sets. In Algorithms and Order (Ottawa, 1987), pages 105\u2013193. Kluwer, Dordrecht, 1989."},{"key":"34_CR34","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0167-8191(98)00100-8","volume":"25","author":"R.H. M\u00f6hring","year":"1999","unstructured":"R.H. M\u00f6hring and M.W. Sch\u00e4ffter. Scheduling series-parallel orders subject to 0\/1-communication delays. Parallel Computing, 25:23\u201340, 1999.","journal-title":"Parallel Computing"},{"key":"34_CR35","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"U. Montanari","year":"1974","unstructured":"U. Montanari. Networks of constraints: Fundamental properties and applications to picture processing. Information Sciences, 7:95\u2013132, 1974.","journal-title":"Information Sciences"},{"key":"34_CR36","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Ta-Shma. Symmetric logspace is closed under complementation. Chicago Journal on Theoretical Computer Science, 1, 1995. (electronic).","DOI":"10.4086\/cjtcs.1995.001"},{"key":"34_CR37","unstructured":"C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994."},{"key":"34_CR38","doi-asserted-by":"crossref","first-page":"165","DOI":"10.3233\/FI-1996-281211","volume":"28","author":"V. Pratt","year":"1996","unstructured":"V. Pratt and J. Tiuryn. Satisfiabilty of inequalities in a poset. Fundamenta Informaticae, 28:165\u2013182, 1996.","journal-title":"Fundamenta Informaticae"},{"key":"34_CR39","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/BF00418652","volume":"7","author":"R.W. Quackenbush","year":"1990","unstructured":"R.W. Quackenbush, I. Rival, and I.G. Rosenberg. Clones, order varieties, nearunaminity functions and holes. Order, 7:239\u2013248, 1990.","journal-title":"Order"},{"key":"34_CR40","doi-asserted-by":"crossref","unstructured":"J.H. Reif. Symmetric complementation. In Proceedings 14th ACM Symposium on Theory of Computing, STOC\u201982, pages 201\u2013214, 1982.","DOI":"10.1145\/800070.802193"},{"key":"34_CR41","doi-asserted-by":"crossref","unstructured":"T.J. Schaefer. The complexity of satisfiability problems. In Proceedings 10th ACM Symposium on Theory of Computing, STOC\u201978, pages 216\u2013226, 1978.","DOI":"10.1145\/800133.804350"},{"key":"34_CR42","volume-title":"Foundations of Constraint Satisfaction","author":"E. Tsang","year":"1993","unstructured":"E. Tsang. Foundations of Constraint Satisfaction. Academic Press, London, 1993."},{"key":"34_CR43","unstructured":"J.D. Ullman. Principles of Database and Knowledge-Base Systems, volume 1 amp; 2. Computer Science Press, 1989."},{"key":"34_CR44","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J. Valdes","year":"1982","unstructured":"J. Valdes, R.E. Tarjan, and E.L. Lawler. The recognition of series-parallel digraphs. SIAM Journal on Computing, 11:298\u2013313, 1982.","journal-title":"SIAM Journal on Computing"},{"key":"34_CR45","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1017\/S0004972700012284","volume":"47","author":"L. Z\u00e1dori","year":"1993","unstructured":"L. Z\u00e1dori. Posets, near-unanimity functions and zigzags. Bulletin of Australian Mathematical Society, 47:79\u201393, 1993.","journal-title":"Bulletin of Australian Mathematical Society"},{"key":"34_CR46","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/BF01108826","volume":"10","author":"L. Z\u00e1dori","year":"1993","unstructured":"L. Z\u00e1dori. Series parallel posets with nonfinitely generated clones. Order, 10:305\u2013316, 1993.","journal-title":"Order"}],"container-title":["Lecture Notes in Computer Science","STACS 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36494-3_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,3]],"date-time":"2020-06-03T10:20:12Z","timestamp":1591179612000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36494-3_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540006237","9783540364948"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/3-540-36494-3_34","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}