Monadic second-order definable text languages
From MaRDI portal
Publication:1361884
DOI10.1007/BF02679464zbMath0872.68096OpenAlexW2060285730MaRDI QIDQ1361884
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
Related Items
Towards a language theory for infinite N-free pomsets. ⋮ 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 ⋮ A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic. ⋮ Multiple context-free tree grammars: lexicalization and characterization ⋮ Weighted Automata and Logics on Infinite Graphs ⋮ Weighted automata ⋮ The recognizability of sets of graphs is a robust property
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
