Search results for "LOGCFL"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
163	Georg Gottlob, Nicola Leone, Francesco Scarcello	Computing LOGCFL Certificates.	ICALP	1999	DBLP DOI BibTeX RDF
88	Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer	The Descriptive Complexity Approach to LOGCFL.	STACS	1999	DBLP DOI BibTeX RDF
67	Georg Gottlob, Christoph Koch 0001, Reinhard Pichler, Luc Segoufin	The complexity of XPath query evaluation and XML typing.	J. ACM	2005	DBLP DOI BibTeX RDF	LOGCFL, XML, Complexity, XPath, DTD
67	Georg Gottlob, Nicola Leone, Francesco Scarcello	The Complexity of Acyclic Conjunctive Queries.	FOCS	1998	DBLP DOI BibTeX RDF	acyclic hypergraph, join tree, LOGCFL, parallel algorithms, computational complexity, database theory, constraint satisfaction problem, conjunctive query, subsumption, query containment, tree query
51	Holger Petersen 0001	The Membership Problem for Regular Expressions with Intersection Is Complete in LOGCFL.	STACS	2002	DBLP DOI BibTeX RDF
51	Egon Wanke	Bounded Tree-Width and LOGCFL.	WG	1993	DBLP DOI BibTeX RDF
37	Nutan Limaye, Meena Mahajan	Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata.	LATA	2009	DBLP DOI BibTeX RDF
37	Michaela Götz, Christoph Koch 0001, Wim Martens	Efficient Algorithms for the Tree Homeomorphism Problem.	DBPL	2007	DBLP DOI BibTeX RDF
37	Carsten Damm, Markus Holzer 0001, Pierre McKenzie	The complexity of tensor calculus.	Comput. Complex.	2002	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000). 15A69, 68Q70, 68Q17, 68Q15, 68Q05
37	Changwook Kim	Efficient recognition algorithms for boundary and linear eNCE graph languages.	Acta Informatica	2001	DBLP DOI BibTeX RDF
37	Carsten Damm, Markus Holzer 0001, Pierre McKenzie	The Complexity of Tensor Calculus.	CCC	2000	DBLP DOI BibTeX RDF
32	Tomoyuki Yamakami	Parameterizations of Logarithmic-Space Reductions, Stack-State Complexity of Nonuniform Families of Pushdown Automata, and a Road to the LOGCFL⊆LOGDCFL/poly Question.	CoRR	2021	DBLP BibTeX RDF
32	Satoru Kuroda	Generalized quantifier and a bounded arithmetic theory for LOGCFL.	Arch. Math. Log.	2007	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 03F30, 68Q15
32	Georg Gottlob, Nicola Leone, Francesco Scarcello	Computing LOGCFL certificates.	Theor. Comput. Sci.	2002	DBLP DOI BibTeX RDF
32	Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer	The Descriptive Complexity Approach to LOGCFL.	J. Comput. Syst. Sci.	2001	DBLP DOI BibTeX RDF
32	Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer	The Descriptive Complexity Approach to LOGCFL	Electron. Colloquium Comput. Complex.	1998	DBLP BibTeX RDF
32	Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer	The descriptive complexity approach to LOGCFL	CoRR	1998	DBLP BibTeX RDF
32	Egon Wanke	Bounded Tree-Width and LOGCFL.	J. Algorithms	1994	DBLP DOI BibTeX RDF
32	H. Venkateswaran	Properties that Characterize LOGCFL.	J. Comput. Syst. Sci.	1991	DBLP DOI BibTeX RDF
32	H. Venkateswaran	Properties that Characterize LOGCFL	STOC	1987	DBLP DOI BibTeX RDF
29	Eric Allender, Klaus-Jörn Lange	Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata.	CCC	2010	DBLP DOI BibTeX RDF	Symmetric Computation, Auxiliary Pushdown Automata, LogCFL, Reversible Computation
29	Georg Gottlob, Nicola Leone, Francesco Scarcello	The complexity of acyclic conjunctive queries.	J. ACM	2001	DBLP DOI BibTeX RDF	LOGCFL, acyclic hypergraph, degree of cyclicity, hinge, join tree, qury-idth, algorithm, parallel algorithm, constraint, CSP, database theory, constraint satisfaction problem, conjunctive query, subsumption, query containment, bounded treewidth, tree query
19	Volker Weber, Thomas Schwentick	Dynamic Complexity Theory Revisited.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
19	Tomasz Jurdzinski	The Boolean Closure of Growing Context-Sensitive Languages.	Developments in Language Theory	2006	DBLP DOI BibTeX RDF
19	Volker Weber, Thomas Schwentick	Dynamic Complexity Theory Revisited.	STACS	2005	DBLP DOI BibTeX RDF
19	Markus Lohrey	Decidability and Complexity in Automatic Monoids.	Developments in Language Theory	2004	DBLP DOI BibTeX RDF
19	Fabrizio Angiulli, Rachel Ben-Eliyahu-Zohary, Giovambattista Ianni, Luigi Palopoli 0001	Computational properties of metaquerying problems.	ACM Trans. Comput. Log.	2003	DBLP DOI BibTeX RDF	data mining, Computational complexity
19	Georg Gottlob, Gianluigi Greco, Francesco Scarcello	Pure Nash equilibria: hard and easy games.	TARK	2003	DBLP DOI BibTeX RDF
19	Georg Gottlob, Christoph Koch 0001, Reinhard Pichler	The complexity of XPath query evaluation.	PODS	2003	DBLP DOI BibTeX RDF	XML
19	Lucian Ilie, Baozhen Shan, Sheng Yu 0001	Fast Algorithms for Extended Regular Expression Matching and Searching.	STACS	2003	DBLP DOI BibTeX RDF	extended regular expressions, algorithms, complexity, pattern matching, finite automata
19	Matthias Galota, Heribert Vollmer	A Generalization of the Büchi-Elgot-Trakhtenbrot Theorem.	CSL	2001	DBLP DOI BibTeX RDF
19	Fabrizio Angiulli, Rachel Ben-Eliyahu-Zohary, Giovambattista Ianni, Luigi Palopoli 0001	Computational Properties of Metaquerying Problems.	PODS	2000	DBLP DOI BibTeX RDF
19	David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum	On Monotone Planar Circuits.	CCC	1999	DBLP DOI BibTeX RDF
19	Klaus Reinhardt, Eric Allender	Making Nondeterminism Unambiguous.	FOCS	1997	DBLP DOI BibTeX RDF	nonuniform complexity, nondeterministic logarithmic space bounded computation, computational complexity, nondeterminism, complexity classes, context-free languages
19	Birgit Jenner	Closure under Complementation of Logspace Complexity Classes - A Survey.	Foundations of Computer Science: Potential - Theory - Cognition	1997	DBLP DOI BibTeX RDF
19	V. Vinay	Hierarchies of Circuit Classes that are Closed under Complement.	CCC	1996	DBLP DOI BibTeX RDF	Circuits, Complexity Theory, Complementation
19	Lance Fortnow, Carsten Lund	Interactive Proof Systems and Alternating Time-Space Complexity.	STACS	1991	DBLP DOI BibTeX RDF
19	Clemens Lautemann	Efficient Algorithms on Context-Free Graph Grammars.	ICALP	1988	DBLP DOI BibTeX RDF