Monadic second-order definable text languages

DOI10.1007/BF02679464zbMath0872.68096MaRDI QIDQ1361884

Hendrik Jan Hoogeboom, Paulien ten Pas

Publication date: 28 July 1997

Published in: Theory of Computing Systems (Search for Journal in Brave)

zbMATH Keywords

text languages

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characterization and complexity of uniformly nonprimitive labeled 2-structures
• T-structures, T-functions, and texts
• Theory of 2-structures. I: Clans, basic subclasses, and morphisms
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• A regular characterization of graph languages definable in monadic second-order logic
• A partial k-arboretum of graphs with bounded treewidth
• Context-free text grammars
• Monadic second-order definable graph transductions: a survey
• The monadic second-order logic of graphs. X: Linear orderings
• 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
• Combinatorial properties of texts
• Algebraic automata and context-free sets
• Generalized finite automata theory with an application to a decision problem of second-order logic