In this article, we consider the interplay of generalized quantifiers and built-in relations over finite structures, in particular, in the range of logics capturing the circuit complexity classes \(\mathrm{AC^{0}}\) and \(\mathrm{TC^{0}}\) . It is well known that for capturing \(\mathrm{AC^{0}}\) first-order logic has to be equipped with order and, e.g., predicates for addition and multiplication, whereas for \(\mathrm{TC^{0}}\) generalized quantifiers such as majority quantifiers are necessary. The sharp division between the classes \(\mathrm{AC^{0}}\) and \(\mathrm{TC^{0}}\) can be explained by the fact that \(\mathrm{AC^{0}}\) is not closed under restricting \(\mathrm{AC^{0}}\) -computable queries into simple subsequences of the input, whereas \(\mathrm{TC^{0}}\) is closed under such relativization as its queries can be expressed in terms of first-order formulas using universe-independent generalized quantifiers and order as the only built-in relation. In the terminology of abstract logics, the above means that logics capturing \(\mathrm{AC^{0}}\) do not have the relativization property, and hence, they are not regular logics unlike the logics capturing \(\mathrm{TC^{0}}\) . This weakness of \(\mathrm{AC^{0}}\) has been also elaborated in the line of research on the Crane Beach Conjecture. The conjecture (which was refuted by Barrington et al.) was that if a language \( L \) has a neutral letter, then \( L \) can be defined in \(\operatorname{FO}_{\mathcal{A}}\) , first-order logic with the collection of all numerical built-in relations \(\mathcal{A}\) , if and only if \( L \) can be already defined in \(\operatorname{FO}_{\leq}\) . Our approach is two-fold. First, we study universe-independent cardinality quantifiers \(\operatorname{\mathsf{Q}}\) defined by a parameter set \(S\subseteq\mathbb{N}\) and formulate a combinatorial criterion for \( S \) implying that all languages in \(\mathrm{DLOGTIME}\) -uniform \(\mathrm{TC^{0}}\) can be defined in \(\operatorname{FO}_{\leq}(\operatorname{\mathsf{Q}})\) . For instance, this criterion is satisfied if \( S \) is the range of some polynomial with positive integer coefficients of degree at least two. Second, by adapting the key properties of abstract logics to accommodate built-in relations, we define the regular interior \(\operatorname{\mathcal{R}-int}(\mathcal{L})\) (the largest regular \(\mathcal{L}^{*}\) such that \(\mathcal{L}^{*}\subseteq\mathcal{L}\) ) and regular closure \(\operatorname{\mathcal{R}-cl}(\mathcal{L})\) (the least regular \(\mathcal{L}^{*}\) such that \(\mathcal{L}\subseteq\mathcal{L}^{*}\) ), of a logic \(\mathcal{L}\) with built-in relations, and show that the Crane Beach Conjecture can be interpreted as a statement concerning the regular interior of \(\mathcal{L}\) . By extending the results of Barrington et al., we further show that if \(\mathcal{B}=\{+\}\) , or \(\mathcal{B}\) contains only unary relations besides \(\leq\) , then \(\operatorname{\mathcal{R}-int}(\operatorname{FO}_{\mathcal{B}})\equiv \operatorname{FO}_{\leq}\) . In contrast, our results from the first part of the article imply that if \(\mathcal{B}\) contains \(\leq\) and the range of a polynomial of degree at least two, then \(\operatorname{\mathcal{R}-cl}(\operatorname{FO}_{\mathcal{B}})\) includes all languages in \(\mathrm{DLOGTIME}\) -uniform \(\mathrm{TC^{0}}\) .