Languages polylog-time reducible to dot-depth 1/2
type: Item
instance of: scholarly article
title: Languages polylog-time reducible to dot-depth 1/2
zbMATH Open document ID: 1178.68315
author: Christian Glaßer
published in: Journal of Computer and System Sciences
publication date: 2007-01-22T00:00:00Z
review text: We study (i) regular languages that are polylog-time reducible to languages of dot-depth 1/2 and (ii) regular languages that are polylog-time decidable. For both classes we provide forbidden-pattern characterizations, and characterizations in terms of regular expressions. This implies that both classes are decidable. In addition, we show that a language is in class (ii) if and only if the language and its complement are in class (i). Our observations have three consequences. (1) Gap theorems for balanced regular-leaf-language definable classes \(\mathcal C\) and \(\mathcal D\) source: (a) Either \(\mathcal C\) is contained in NP, or \(\mathcal C\) contains coUP. (b) Either \(\mathcal D\) is contained in P, or \(\mathcal D\) contains UP or coUP. We also extend both theorems such that no promise classes are involved. Formerly, such gap theorems were known only for the unbalanced approach. (2) Polylog-time reductions can tremendously decrease dot-depth complexity (despite that these reductions cannot count). We construct languages of arbitrary dot-depth that are reducible to languages of dot-depth 1/2. (3) Unbalanced star-free leaf languages can be much stronger than balanced ones. We construct star-free regular languages \(L_n\) such that \(L_n\)'s balanced leaf-language class is NP, but the unbalanced leaf-language class of \(L_n\) contains level n of the unambiguous alternation hierarchy. This demonstrates the power of unbalanced computations.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 5117736
zbMATH Keywords: dot-depth
zbMATH Keywords: leaf languages
zbMATH Keywords: polylog-time reductions
zbMATH Keywords: forbidden patterns
MaRDI profile type: Publication
full work available at URL: j.jcss.2006.09.004
OpenAlex ID: W2114279245
cites work: Polynomial operations and hierarchies of concatenation
cites work: Regular languages in \(NC\)
cites work: On the unique satisfiability problem
cites work: On the acceptance power of regular languages
cites work: On Existentially First-Order Definable Languages and Their Relation to NP
cites work: A uniform approach to define complexity classes
cites work: The dot-depth hierarchy of star-free languages is infinite
cites work: LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY
cites work: Dot-depth of star-free events
cites work: Q4132170
cites work: Simultaneous strong separations of probabilistic and unambiguous complexity classes
cites work: Gap-definable counting classes
cites work: Q4501562
cites work: Q3764142
cites work: Threshold Computation and Cryptographic Security
cites work: Q3673124
cites work: Programs over semigroups of dot-depth one
cites work: Q5641083
cites work: Unambiguous computations and locally definable acceptance types
cites work: A complexity theory for feasible closure properties
cites work: Finite semigroup varieties defined by programs
cites work: First-order logic and star-free sets
cites work: Eilenberg's theorem for positive varieties of languages
cites work: Some results onC-varieties
cites work: Polynomial closure and unambiguous product
cites work: THE WREATH PRODUCT PRINCIPLE FOR ORDERED SEMIGROUPS
cites work: On finite monoids having only trivial subgroups
cites work: A reducibility for the dot-depth hierarchy
cites work: Fundamentals of Computation Theory
cites work: Finite semigroup varieties of the form V*D
cites work: An application of the Ehrenfeucht-Fraisse game in formal language theory
cites work: RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
DOI: 10.1016/J.JCSS.2006.09.004
description: scientific article; zbMATH DE number 5117736