Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures

DOI10.1016/S0304-3975(01)00277-8zbMath0992.68128MaRDI QIDQ5958302

Oliver Matz

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

monadic second-order logicstarfree picture languagestarfree word languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (5)

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures