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 logic; starfree picture language; starfree word languages

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q42: Grammars and rewriting systems

Related Items

Deterministic and unambiguous two-dimensional languages over one-letter alphabet, The monadic quantifier alternation hierarchy over grids and graphs, Classes of two-dimensional languages and recognizability conditions, Recognizable vs. Regular Picture Languages, Deterministic 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