Hierarchies and reducibilities on regular languages related to modulo counting
DOI10.1051/ITA:2007063zbMATH Open1174.03016OpenAlexW2115184558MaRDI QIDQ3549290FDOQ3549290
Authors: Victor Selivanov 
Publication date: 22 December 2008
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/92909
Recommendations
complexity classesregular languageforbidden patterndifference hierarchyfinite structurespolylogtime reducibilityquantifier-alternation hierarchyquantifier-free reducibility
Model theory of finite structures (03C13) Automata and formal grammars in connection with logical questions (03D05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- A uniform approach to define complexity classes
- Title not available (Why is that?)
- RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
- Title not available (Why is that?)
- Title not available (Why is that?)
- On finite monoids having only trivial subgroups
- Classifying regular events in symbolic logic
- Title not available (Why is that?)
- Title not available (Why is that?)
- Characterizations of some classes of regular events
- First-order logic and star-free sets
- Regular languages in \(NC\)
- Polynomial closure and unambiguous product
- Dot-depth of star-free events
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Languages polylog-time reducible to dot-depth 1/2
- Regular languages defined with generalized quantifiers
- Topology and descriptive set theory
- A reducibility for the dot-depth hierarchy
- On ω-regular sets
- Title not available (Why is that?)
- Title not available (Why is that?)
- Algebraic decision procedures for local testability
- Fine Hierarchy of Regular Aperiodic ω-Languages
- Title not available (Why is that?)
- On the acceptance power of regular languages
- Title not available (Why is that?)
- Actions, wreath products of \(\mathcal C\)-varieties and concatenation product.
- An application of the Ehrenfeucht-Fraisse game in formal language theory
- On Existentially First-Order Definable Languages and Their Relation to NP
- Machines, Computations, and Universality
- Title not available (Why is that?)
- Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
- The chain method to separate counting classes
- New Computational Paradigms
- STACS 2005
- Mathematical Foundations of Computer Science 2004
Cited In (20)
- Mathematical Foundations of Computer Science 2004
- Title not available (Why is that?)
- Extending Wagner's hierarchy to deterministic visibly pushdown automata
- Logic vs topology on regular \(\omega \)-languages
- Fine hierarchies via Priestley duality
- The Boolean algebra of piecewise testable languages
- Title not available (Why is that?)
- Fine hierarchies and m-reducibilities in theoretical computer science
- Efficient algorithms for membership in Boolean hierarchies of regular languages
- Moore reducibility for regular languages
- Title not available (Why is that?)
- New Computational Paradigms
- Title not available (Why is that?)
- Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
- A reducibility for the dot-depth hierarchy
- Some uncountable hierarchies of formal languages
- A survey on difference hierarchies of regular languages
- Well-Quasi Orders and Hierarchy Theory
- Boolean algebras of regular languages
- Title not available (Why is that?)
This page was built for publication: Hierarchies and reducibilities on regular languages related to modulo counting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3549290)
