Languages of dot-depth 3/2

DOI10.1007/S00224-007-9002-0MaRDI QIDQ2480745zbMATH OpenOpenAlexFDO

Authors Christian Glaßer, H. Schmitz

Publication date 3 April 2008

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-007-9002-0

zbMATH Keywords

Concatenation hierarchiesDecidabilityDot-depth hierarchyStarfree regular languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 1500543
• On a conjecture concerning dot-depth two languages
• scientific article; zbMATH DE number 3961008
• Semigroups and languages of dot-depth two
• Languages polylog-time reducible to dot-depth 1/2
• scientific article; zbMATH DE number 2150293
• On Some Classes of 2D Languages and Their Relations
• Languages of Nested Trees
• Languages and P0L schemes
• Three algebraic representation levels of the language

Cites work

• A generalization of the Schützenberger product of finite monoids
• Algebraic decision procedures for local testability
• An application of the Ehrenfeucht-Fraisse game in formal language theory
• Classification of finite monoids: the language approach
• Classifying regular events in symbolic logic
• Dot-depth of star-free events
• Finite semigroup varieties of the form V*D
• scientific article; zbMATH DE number 4035179 (Why is no real title available?)
• scientific article; zbMATH DE number 4087055 (Why is no real title available?)
• scientific article; zbMATH DE number 1223722 (Why is no real title available?)
• scientific article; zbMATH DE number 2080228 (Why is no real title available?)
• scientific article; zbMATH DE number 1500543 (Why is no real title available?)
• scientific article; zbMATH DE number 2087228 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2004
• Nondeterministic Space is Closed under Complementation
• On finite monoids having only trivial subgroups
• Polynomial closure and unambiguous product
• Polynomial operations and hierarchies of concatenation
• Semigroups and languages of dot-depth two
• The dot-depth hierarchy of star-free languages is infinite
• THE WREATH PRODUCT PRINCIPLE FOR ORDERED SEMIGROUPS

Cited in

(17)

• Triple dots in a formal language
• Complexity of universality and related problems for partially ordered NFAs
• Varieties
• Generic results for concatenation hierarchies
• Concatenation hierarchies: new bottle, old wine
• The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy
• Three algebraic representation levels of the language
• Theme and variations on the concatenation product
• Efficient algorithms for membership in Boolean hierarchies of regular languages
• Around dot depth two
• scientific article; zbMATH DE number 1500543 (Why is no real title available?)
• Around dot-depth one
• Forbidden patterns for ordered automata
• Partially ordered automata and piecewise testability
• Forbidden Patterns for FO² Alternation Over Finite and Infinite Words
• Closing star-free closure
• Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words

This page was built for publication: Languages of dot-depth 3/2

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