1. Specifying graph languages with type graphs
- Author
-
Andrea Corradini, Barbara König, and Dennis Nolte
- Subjects
FOS: Computer and information sciences ,Computer Science - Logic in Computer Science ,Dense graph ,Formal Languages and Automata Theory (cs.FL) ,Logic ,Computer science ,Symmetric graph ,Comparability graph ,Computer Science - Formal Languages and Automata Theory ,Theoretical Computer Science ,Computer Science (all) ,02 engineering and technology ,0102 computer and information sciences ,Type graph ,01 natural sciences ,law.invention ,Combinatorics ,Indifference graph ,Pathwidth ,Chordal graph ,law ,Partial k-tree ,Line graph ,0202 electrical engineering, electronic engineering, information engineering ,Cograph ,Split graph ,Pancyclic graph ,Forbidden graph characterization ,Universal graph ,Block graph ,Discrete mathematics ,Graph rewriting ,Lévy family of graphs ,020207 software engineering ,1-planar graph ,Rotation formalisms in three dimensions ,Graph ,Logic in Computer Science (cs.LO) ,Decidability ,Modular decomposition ,Treewidth ,Informatik ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Topological graph theory ,Graph product ,Software ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
We investigate three formalisms to specify graph languages, i.e. sets of graphs, based on type graphs. First, we are interested in (pure) type graphs, where the corresponding language consists of all graphs that can be mapped homomorphically to a given type graph. In this context, we also study languages specified by restriction graphs and their relation to type graphs. Second, we extend this basic approach to a type graph logic and, third, to type graphs with annotations. We present decidability results and closure properties for each of the formalisms., (v2): -Fixed some typos -Added more references more...
- Published
- 2019
- Full Text
- View/download PDF