Monadic second-order definable text languages

DOI10.1007/BF02679464MaRDI QIDQ1361884zbMATH OpenOpenAlexFDO

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

• 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
• 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?)
• 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)

• 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.
• Weighted automata
• The recognizability of sets of graphs is a robust property
• Weighted automata and logics on infinite graphs
• A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic.
• MSO definable text languages
• Existential MSO over two successors is strictly weaker than over linear orders
• Definable transductions and weighted logics for texts
• Axiomatizing the identities of binoid languages

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)