Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures
From MaRDI portal
Publication:5958302
DOI10.1016/S0304-3975(01)00277-8zbMath0992.68128MaRDI QIDQ5958302
Publication date: 3 March 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
Recognizable vs. Regular Picture Languages ⋮ Deterministic Two-Dimensional Languages over One-Letter Alphabet ⋮ Classes of two-dimensional languages and recognizability conditions ⋮ The monadic quantifier alternation hierarchy over grids and graphs ⋮ Deterministic and unambiguous two-dimensional languages over one-letter alphabet
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finite automata and unary languages
- The dot-depth hierarchy of star-free languages is infinite
- Context-sensitive string languages and recognizable picture languages
- Monadic second-order logic over rectangular pictures and recognizability by tiling systems
- The monadic quantifier alternation hierarchy over grids and graphs
- On the maximal order in $S_n$ and $S*_n$
- Star-free picture expressions are strictly weaker than first-order logic