Language theoretic properties of regular DAG languages

DOI10.1016/J.IC.2017.07.011MaRDI QIDQ2272978zbMATH OpenOpenAlexWikidataFDO

Authors Johannes Blum, Frank Drewes

Publication date 17 September 2019

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2017.07.011

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Properties of regular DAG languages
• scientific article; zbMATH DE number 4009839
• On the regularity and learnability of ordered DAG languages
• scientific article; zbMATH DE number 3848634
• Regular languages viewed from a graph-theoretic perspective
• Deterministic regular languages
• scientific article; zbMATH DE number 1244205
• Duality and Equational Theory of Regular Languages
• Towards a theory of complexity of regular languages
• Regular languages and partial commutations

Cites work

• Applications of weighted automata in natural language processing
• Closure properties and decision problems of dag automata
• Finite Automata on Unranked and Unordered DAGs
• Graph structure and monadic second-order logic. A language-theoretic approach
• Handbook of Graph Grammars and Computing by Graph Transformation
• Hyperedge replacement: grammars and languages
• Nondeterminism versus determinism of finite automata over directed acyclic graphs
• Parallel and two-way automata on directed ordered acyclic graphs
• Properties of regular DAG languages
• Structurally cyclic Petri nets

Cited in

(15)

• Closure properties and decision problems of dag automata
• Syntactic structures of regular languages
• On bigram languages
• On the regularity and learnability of ordered DAG languages
• Properties of regular DAG languages
• Some Examples of Semi-rational DAG Languages
• scientific article; zbMATH DE number 4072412 (Why is no real title available?)
• DAG automata for meaning representation
• (Re)introducing regular graph languages
• On DAG languages and DAG transducers
• Regular languages viewed from a graph-theoretic perspective
• Developments in Language Theory
• Homomorphic definitions of tree languages via comma-free tree codes
• Winning strategies for the synchronization game on subclasses of finite automata
• A new notion of regularity: finite state automata accepting graphs

This page was built for publication: Language theoretic properties of regular DAG languages

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