Monadic second-order definable text languages

DOI10.1007/BF02679464zbMATH Open0872.68096OpenAlexW2060285730MaRDI QIDQ1361884FDOQ1361884

Authors: Hendrik Jan Hoogeboom, Paulien ten Pas 

Publication date: 28 July 1997

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

Full work available at URL: https://doi.org/10.1007/bf02679464

Recommendations

• MSO definable text languages
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A regular characterization of graph languages definable in monadic second-order logic
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• scientific article; zbMATH DE number 17791

zbMATH Keywords

text languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• A partial k-arboretum of graphs with bounded treewidth
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Monadic second-order definable graph transductions: a survey
• Title not available (Why is that?)
• Weak Second‐Order Arithmetic and Finite Automata
• Generalized finite automata theory with an application to a decision problem of second-order logic
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• Theory of 2-structures. I: Clans, basic subclasses, and morphisms
• Tree acceptors and some of their applications
• Algebraic automata and context-free sets
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• The monadic second-order logic of graphs. X: Linear orderings
• Title not available (Why is that?)
• Characterization and complexity of uniformly nonprimitive labeled 2-structures
• T-structures, T-functions, and texts
• A regular characterization of graph languages definable in monadic second-order logic
• Context-free text grammars
• Title not available (Why is that?)
• Combinatorial properties of texts

Cited In (10)

• Definable transductions and weighted logics for texts
• Languages recognized by programs over the two-element monoid
• Multiple context-free tree grammars: lexicalization and characterization
• Towards a language theory for infinite N-free pomsets.
• Axiomatizing the identities of binoid languages
• A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic.
• Weighted Automata and Logics on Infinite Graphs
• The recognizability of sets of graphs is a robust property
• Existential MSO over two successors is strictly weaker than over linear orders
• Weighted automata

This page was built for publication: Monadic second-order definable text languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1361884)