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

DOI10.1016/J.JCSS.2006.09.004MaRDI QIDQ859980zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

forbidden patternsleaf languagesdot-depthpolylog-time reductions

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

Cites work

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

Cited in

(12)

• Perfect correspondences between dot-depth and polynomial-time hierarchies
• Hierarchies and reducibilities on regular languages related to modulo counting
• scientific article; zbMATH DE number 1500543 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 1361492 (Why is no real title available?)
• STACS 2005
• Languages of dot-depth 3/2
• Developments in Language Theory
• 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)