Uniform and nonuniform recognizability.

DOI10.1016/S0304-3975(01)00229-8zbMath1064.68059MaRDI QIDQ1853746

Wolfgang Thomas

Publication date: 22 January 2003

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

zbMATH Keywords

RecognizabilityPicture languagesMonadic second-order logicGraph languageTree language

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Algebraic theory of languages and automata (68Q70)

Cites Work

• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• The monadic second-order logic of graphs. XIII: Graph drawings with edge crossings
• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• Tree acceptors and some of their applications
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Weak Second‐Order Arithmetic and Finite Automata
• Decision Problems of Finite Automata Design and Related Arithmetics
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Uniform and nonuniform recognizability.