Search results for "alternating Turing machine"

Found 16 publication records. Showing 16 according to the selection in the facets

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
2	Liming Cai, Jianer Chen, Johan Håstad	Circuit Bottom Fan-in and Computational Power. (PDF / PS)	IEEE Conference on Computational Complexity	1997	DBLP DOI BibTeX RDF	computational complexity, lower bound, circuit complexity, alternating Turing machine
2	Tao Jiang	On the Complexity of (Off-Line) 1-Tape ATM's Running in Constant Reversals.	ICCI	1990	DBLP DOI BibTeX RDF	1-tape, off-line 1-tape, head reversal, computational complexity, alternating Turing machine
1	Mohamed Faouzi Atig, Benedikt Bollig, Peter Habermehl	Emptiness of Multi-pushdown Automata Is 2ETIME-Complete.	Developments in Language Theory	2008	DBLP DOI BibTeX RDF
1	Dariusz Kusmierek	The Inhabitation Problem for Rank Two Intersection Types.	TLCA	2007	DBLP DOI BibTeX RDF	type inhabitation problem, lambda calculus, intersection types, alternating Turing machine
1	Holger Spakowski, Rahul Tripathi	On the Power of Unambiguity in Alternating Machines.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
1	Guillaume Bonfante, Jean-Yves Marion, Romain Péchoux	A Characterization of Alternating Log Time by First Order Functional Programs.	LPAR	2006	DBLP DOI BibTeX RDF
1	Holger Spakowski, Rahul Tripathi	On the Power of Unambiguity in Alternating Machines.	FCT	2005	DBLP DOI BibTeX RDF
1	Pei-Chi Wu	On exponential-time completeness of the circularity problem for attribute grammars.	ACM Trans. Program. Lang. Syst.	2004	DBLP DOI BibTeX RDF	EXPTIME-complete, circularity problem, Attribute grammars, alternating Turing machines
1	Hubert Comon, Florent Jacquemard	Ground Reducibility is EXPTIME-Complete.	LICS	1997	DBLP DOI BibTeX RDF
1	Kai Salomaa, Derick Wood, Sheng Yu	Complexity of E0L Structural Equivalence.	MFCS	1994	DBLP DOI BibTeX RDF
1	Klaus Reinhardt	Hierarchies over the Context-Free Languages.	IMYCS	1990	DBLP DOI BibTeX RDF
1	Marek Priotrów	ATIME(N) is Closed Under Counting.	MFCS	1990	DBLP DOI BibTeX RDF
1	V. S. Lakshmanan, Alberto O. Mendelzon	Inductive Pebble Games and the Expressive Power of Datalog.	PODS	1989	DBLP DOI BibTeX RDF	Datalog
1	Jeffrey D. Ullman, Moshe Y. Vardi	The Complexity of Ordering Subgoals.	PODS	1988	DBLP DOI BibTeX RDF
1	Erich Grädel	Domino Games with an Application to the Complexity of Boolean Algebras with Bounded Quantifier Alternations.	STACS	1988	DBLP DOI BibTeX RDF
1	Udi Manber, Martin Tompa	The Complexity of Problems on Probabilistic Nondeterministic, and Alternating Decision Trees	J. ACM	1985	DBLP DOI BibTeX RDF