scientific article; zbMATH DE number 1396734
The author uses a specific truth notion for the first-order sentences on syntactical expressions (words as particular cases) over nontrivial alphabets. This truth notion leads to an arithmetical-like hierarchy \(\{S_k\}_{k<\omega}\) of languages based on the number of quantifier alternations in the prefix of a formula. The author defines a refinement of this hierarchy, namely, the difference hierarchy over the last hierarchy whose classes \(D_{k,l}\) consist of \[ \bigcup_{i=1}^m(L_{2i-1}\setminus L_{2i}),\;m\in N,\;L_i\in S_k\;\hbox{for} 1\leq i\leq j\;\hbox{and} L_i=\emptyset\;\hbox{for} i>l, \] and proves it to be nontrivial.
- A survey on difference hierarchies of regular languages
- Difference hierarchies and duality with an application to formal languages
- Going Higher in First-Order Quantifier Alternation Hierarchies on Words
- Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
- Hierarchies and reducibilities on regular languages related to modulo counting
- Difference hierarchies and duality with an application to formal languages
- A reducibility for the dot-depth hierarchy
- Efficient algorithms for membership in Boolean hierarchies of regular languages
- Hierarchies and reducibilities on regular languages related to modulo counting
- scientific article; zbMATH DE number 1534571 (Why is no real title available?)
- A survey on difference hierarchies of regular languages
- scientific article; zbMATH DE number 2086619 (Why is no real title available?)
- Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
- Fine hierarchies and m-reducibilities in theoretical computer science
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4936686)
