Languages polylog-time reducible to dot-depth 1/2

DOI10.1016/J.JCSS.2006.09.004zbMATH Open1178.68315OpenAlexW2114279245MaRDI QIDQ859980FDOQ859980

Christian Glaßer

Publication date: 22 January 2007

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2006.09.004

Recommendations

• STACS 2005
• Perfect correspondences between dot-depth and polynomial-time hierarchies
• Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy
• New Computational Paradigms
• Logspace and logtime leaf languages

zbMATH Keywords

forbidden patternsleaf languagesdot-depthpolylog-time reductions

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• A uniform approach to define complexity classes
• Title not available (Why is that?)
• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• On finite monoids having only trivial subgroups
• Title not available (Why is that?)
• First-order logic and star-free sets
• Regular languages in \(NC\)
• Polynomial closure and unambiguous product
• Programs over semigroups of dot-depth one
• Finite semigroup varieties of the form V*D
• Dot-depth of star-free events
• Title not available (Why is that?)
• THE WREATH PRODUCT PRINCIPLE FOR ORDERED SEMIGROUPS
• LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY
• A reducibility for the dot-depth hierarchy
• Gap-definable counting classes
• A complexity theory for feasible closure properties
• Threshold Computation and Cryptographic Security
• On the unique satisfiability problem
• On the acceptance power of regular languages
• The dot-depth hierarchy of star-free languages is infinite
• Eilenberg's theorem for positive varieties of languages
• Some results onC-varieties
• Polynomial operations and hierarchies of concatenation
• Unambiguous computations and locally definable acceptance types
• Finite semigroup varieties defined by programs
• An application of the Ehrenfeucht-Fraisse game in formal language theory
• Title not available (Why is that?)
• Simultaneous strong separations of probabilistic and unambiguous complexity classes
• Title not available (Why is that?)
• On Existentially First-Order Definable Languages and Their Relation to NP
• Fundamentals of Computation Theory

Cited In (11)

• Hierarchies and reducibilities on regular languages related to modulo counting
• Title not available (Why is that?)
• Dot operators
• Fine hierarchies and m-reducibilities in theoretical computer science
• Efficient algorithms for membership in Boolean hierarchies of regular languages
• Machines that can output empty words
• Title not available (Why is that?)
• STACS 2005
• Developments in Language Theory
• Languages of dot-depth 3/2
• Machines that Can Output Empty Words

This page was built for publication: Languages polylog-time reducible to dot-depth 1/2

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q859980)