MSO definable text languages

DOI10.1007/3-540-58338-6_88MaRDI QIDQ5096900zbMATH OpenOpenAlexFDO

Authors Hendrik Jan Hoogeboom, Paulien ten Pas

Publication date 18 August 2022

Published in Mathematical Foundations of Computer Science 1994 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-58338-6_88

Mathematics Subject Classification ID

Higher-order logic (03B16) Automata and formal grammars in connection with logical questions (03D05) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• Monadic second-order definable text languages
• scientific article; zbMATH DE number 871246
• T-structures, T-functions, and texts
• Context-free text grammars
• Definable Transductions and Weighted Logics for Texts

Cites work

• A regular characterization of graph languages definable in monadic second-order logic
• Algebraic automata and context-free sets
• 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 3854429 (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 871246 (Why is no real title available?)
• scientific article; zbMATH DE number 3227055 (Why is no real title available?)
• 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
• 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

(8)

• Context-free text grammars
• Monadic second-order definable text languages
• The monadic second-order logic of graphs. X: Linear orderings
• Data monoids
• Definable Transductions and Weighted Logics for Texts
• T-structures, T-functions, and texts
• Existential MSO over two successors is strictly weaker than over linear orders
• EMSO-definability of some languages with event structures

This page was built for publication: MSO definable text languages

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