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

zbMATH Keywords

text languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

Cites work

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

Cited in

(11)

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