ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Digital Library logoTake a look at the new version of this page: [ beta version ]. Tell us what you think.
Graph rewriting: an algebraic and logic approach
Source
Handbook of theoretical computer science (vol. B): formal models and semantics book contents
Pages: 193 - 242  
Year of Publication: 1991
ISBN:0-444-88074-7
Author
Brouno Courcelle
Publisher
MIT Press  Cambridge, MA, USA
Bibliometrics
Downloads (6 Weeks): n/a,   Downloads (12 Months): n/a,   Citation Count: 60
Additional Information:

cited by   index terms  

Tools and Actions: Review this Article  

CITED BY  60
Stefan Arnborg , Bruno Courcelle , Andrzej Proskurowski , Detlef Seese, An algebraic theory of graph reduction, Journal of the ACM (JACM), v.40 n.5, p.1134-1164, Nov. 1993
Martin Grohe, Computing crossing numbers in quadratic time, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.231-236, July 2001, Hersonissos, Greece
Martin Grohe, The parameterized complexity of database queries, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.82-92, May 2001, Santa Barbara, California, United States
Georg Gottlob , Christoph Koch, Monadic datalog and the expressive power of languages for web information extraction, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
Pascal Fradet , Daniel Le Métayer, Shape types, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.27-39, January 15-17, 1997, Paris, France
Georg Gottlob , Erich Grädel , Helmut Veith, Datalog LITE: a deductive query language with linear time model checking, ACM Transactions on Computational Logic (TOCL), v.3 n.1, p.42-79, January 2002
Michel Bauderon , Hélène Jacquet, Node rewriting in graphs and hypergraphs: a categorical framework, Theoretical Computer Science, v.266 n.1-2, p.463-487, 09/06/2001
Mizuhito Ogawa , Zhenjiang Hu , Isao Sasano, Iterative-free program analysis, ACM SIGPLAN Notices, v.38 n.9, p.111-123, September 2003
Daniel Le Métayer, Software architecture styles as graph grammars, ACM SIGSOFT Software Engineering Notes, v.21 n.6, p.15-23, Nov. 1996
Jörg Flum , Markus Frick , Martin Grohe, Query evaluation via tree-decompositions, Journal of the ACM (JACM), v.49 n.6, p.716-752, November 2002
Frank Neven , Thomas Schwentick, Query automata over finite trees, Theoretical Computer Science, v.275 n.1-2, p.633-674, March 28 2002
J. A. Makowsky , J. P. Mariño, The parametrized complexity of knot polynomials, Journal of Computer and System Sciences, v.67 n.4, p.742-756, December 2003
Martin Grohe, Computing crossing numbers in quadratic time, Journal of Computer and System Sciences, v.68 n.2, p.285-302, March 2004
Markus Frick , Martin Grohe, Deciding first-order properties of locally tree-decomposable structures, Journal of the ACM (JACM), v.48 n.6, p.1184-1206, November 2001
Isao Sasano , Zhenjiang Hu , Masato Takeichi , Mizuhito Ogawa, Make it practical: a generic linear-time algorithm for solving maximum-weightsum problems, ACM SIGPLAN Notices, v.35 n.9, p.137-149, Sept. 2000
Georg Gottlob , Christoph Koch, Monadic datalog and the expressive power of languages for Web information extraction, Journal of the ACM (JACM), v.51 n.1, p.74-113, January 2004
Martin Grohe, Parameterized complexity for the database theorist, ACM SIGMOD Record, v.31 n.4, December 2002
Wolfgang Thomas, Uniform and nonuniform recognizability, Theoretical Computer Science, v.292 n.1, p.299-316, January 2003
Frank Neven , Thomas Schwentick , Victor Vianu, Finite state machines for strings over infinite alphabets, ACM Transactions on Computational Logic (TOCL), v.5 n.3, p.403-435, July 2004
Daniel Le Métayer, Describing Software Architecture Styles Using Graph Grammars, IEEE Transactions on Software Engineering, v.24 n.7, p.521-533, July 1998
Didier Caucal, On infinite transition graphs having a decidable monadic theory, Theoretical Computer Science, v.290 n.1, p.79-115, 1 January 2003
Teodor Rus, A unified language processing methodology, Theoretical Computer Science, v.281 n.1-2, p.499-536, June 3 2002
Didier Caucal, On the transition graphs of Turing machines, Theoretical Computer Science, v.296 n.2, p.195-223, 8 March 2003
Hans-Peter Kolb , Jens Michaelis , Uwe Mönnich , Frank Morawietz, An operational and denotational approach to non-context-freeness, Theoretical Computer Science, v.293 n.2, p.261-289, 6 February 2003
Zoltán Fülöp , Heiko Vogler, Weighted tree transducers, Journal of Automata, Languages and Combinatorics, v.9 n.1, p.31-54, January 2004
Piero A. Bonatti, On the decidability of containment of recursive datalog queries - preliminary report, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
Georg Gottlob , Christoph Koch , Robert Baumgartner , Marcus Herzog , Sergio Flesca, The Lixto data extraction project: back and forth between theory and practice, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
Erik D. Demaine , Fedor V. Fomin , Mohammadtaghi Hajiaghayi , Dimitrios M. Thilikos, Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs, ACM Transactions on Algorithms (TALG), v.1 n.1, p.33-47, July 2005
Foto Afrati , Stavros Cosmadakis , Eugénie Foustoucos, Datalog programs and their persistency numbers, ACM Transactions on Computational Logic (TOCL), v.6 n.3, p.481-518, July 2005
Georg Gottlob , Christoph Koch, Logic-based web information extraction, ACM SIGMOD Record, v.33 n.2, June 2004
Ton Kloks , Dieter Kratsch , Chuan-Min Lee , Jiping Liu, Improved bottleneck domination algorithms, Discrete Applied Mathematics, v.154 n.11, p.1578-1592, 1 July 2006
O. A. Shcherbina, Tree decomposition and discrete optimization problems: A survey, Cybernetics and Systems Analysis, v.43 n.4, p.549-562, July 2007
Christoph Koch, Processing queries on tree-structured data efficiently, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
Jaroslav Nešetřil , Patrice Ossona de Mendez, Linear time low tree-width partitions and algorithmic consequences, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Georg Gottlob , Reinhard Pichler , Fang Wei, Tractable database design through bounded treewidth, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
Stephan Kepser, Using MONA for querying linguistic treebanks, Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, p.555-562, October 06-08, 2005, Vancouver, British Columbia, Canada
Erik D. Demaine , Mohammad Taghi Hajiaghayi, Quickly deciding minor-closed parameters in general graphs, European Journal of Combinatorics, v.28 n.1, p.311-314, January 2007
Georg Gottlob , Zoltan Miklos , Thomas Schwentick, Generalized hypertree decompositions: np-hardness and tractable variants, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
Karl-Heinz Pennemann, An Algorithm for Approximating the Satisfiability Problem of High-level Conditions, Electronic Notes in Theoretical Computer Science (ENTCS), v.213 n.1, p.75-94, May, 2008
Georg Gottlob , Reinhard Pichler , Fang Wei, Monadic datalog over finite structures with bounded treewidth, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
Georg Gottlob , Stephanie Tien Lee, A logical approach to multicut problems, Information Processing Letters, v.103 n.4, p.136-141, August, 2007
Ken-ichi Kawarabayashi , Buce Reed, Computing crossing number in linear time, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
Iain A. Stewart, On the fixed-parameter tractability of parameterized model-checking problems, Information Processing Letters, v.106 n.1, p.33-36, March, 2008
Peter Buneman , Mary Fernandez , Dan Suciu, UnQL: a query language and algebra for semistructured data based on structural recursion, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.1, p.76-110, March 2000
Stephan Kepser, Querying Linguistic Treebanks with Monadic Second-Order Logic in Linear Time, Journal of Logic, Language and Information, v.13 n.4, p.457-470, March 2004
Paul Hunter , Stephan Kreutzer, Digraph measures: Kelly decompositions, games, and orderings, Theoretical Computer Science, v.399 n.3, p.206-219, June, 2008
Michael Benedikt , Christoph Koch, XPath leashed, ACM Computing Surveys (CSUR), v.41 n.1, p.1-54, December 2008
Paul Hunter , Stephan Kreutzer, Digraph measures: Kelly decompositions, games, and orderings, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.637-644, January 07-09, 2007, New Orleans, Louisiana
Isolde Adler , Martin Grohe , Stephan Kreutzer, Computing excluded minors, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.641-650, January 20-22, 2008, San Francisco, California
Martin Strecker, Modeling and Verifying Graph Transformations in Proof Assistants, Electronic Notes in Theoretical Computer Science (ENTCS), v.203 n.1, p.135-148, March, 2008
Georg Gottlob , Reinhard Pichler , Fang Wei, Bounded treewidth as a key to tractability of knowledge representation and reasoning, Proceedings of the 21st national conference on Artificial intelligence, p.250-256, July 16-20, 2006, Boston, Massachusetts
Annegret Habel , Karl-heinz Pennemann, Correctness of high-level transformation systems relative to nested conditions†, Mathematical Structures in Computer Science, v.19 n.2, p.245-296, April 2009
Eugénie Foustoucos , Labrini Kalantzi, The Monadic Second-order Logic Evaluation Problem on Finite Colored Trees: a Database-theoretic Approach, Fundamenta Informaticae, v.92 n.3, p.193-231, August 2009
Georg Gottlob , Reinhard Pichler , Fang Wei, Abduction with bounded treewidth: from theoretical tractability to practically efficient computation, Proceedings of the 23rd national conference on Artificial intelligence, p.1541-1546, July 13-17, 2008, Chicago, Illinois
Georg Gottlob , Reinhard Pichler , Fang Wei, Efficient datalog abduction through bounded treewidth, Proceedings of the 22nd national conference on Artificial intelligence, p.1626-1631, July 22-26, 2007, Vancouver, British Columbia, Canada
Michael Jakl , Reinhard Pichler , Stefan Woltran, Answer-set programming with bounded treewidth, Proceedings of the 21st international jont conference on Artifical intelligence, p.816-822, July 11-17, 2009, Pasadena, California, USA
Gianluigi Greco , Enrico Malizia , Luigi Palopoli , Francesco Scarcello, On the complexity of compact coalitional games, Proceedings of the 21st international jont conference on Artifical intelligence, p.147-152, July 11-17, 2009, Pasadena, California, USA
Georg Gottlob , Reinhard Pichler , Fang Wei, Bounded treewidth as a key to tractability of knowledge representation and reasoning, Artificial Intelligence, v.174 n.1, p.105-132, January, 2010
Joachim Kneis , Alexander Langer, A Practical Approach to Courcelle's Theorem, Electronic Notes in Theoretical Computer Science (ENTCS), 251, p.65-81, September, 2009
Georg Gottlob , Zoltán Miklós , Thomas Schwentick, Generalized hypertree decompositions: NP-hardness and tractable variants, Journal of the ACM (JACM), v.56 n.6, p.1-32, September 2009

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Complexity hierarchies
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES


General Terms:
Languages, Theory, Verification


The ACM Portal is published by the Association for Computing Machinery. Copyright © 2010 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player