8 citations · 10 across the 2 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2005★ 2 cited
The Complexity of Computing the Size of an Interval
Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub +1
Given a p-order A over a universe of strings (i.e., a transitive, reflexive, antisymmetric relation such that if (x, y) is an element of A then |x| is polynomially bounded by |y|),…
cs.CC1998★ 8 cited
The Boolean Hierarchy over Level 1/2 of the Straubing-Therien Hierarchy
Heinz Schmitz, Klaus W. Wagner
For some fixed alphabet A, a language L of A* is in the class L(1/2) of the Straubing-Therien hierarchy if and only if it can be expressed as a finite union of languages A*aA*bA*..…