Details

Autor(en) / Beteiligte

• Wanke, Egon
• Budach, L.

Titel

On the decidability of integer subgraph problems on context-free graph languages

Ist Teil von

• Fundamentals of Computation Theory, 2005, p.415-426

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Erscheinungsjahr

2005

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• We show the decidability of integer subgraph problems (ISPs) on context-free sets of graphs L(Γ) defined by hyperedge replacement systems (HRSs) Γ. Additionally, we give a very general characterization of ISPs to be decidable on a set L(Γ). An ISP ∏ consists of a property s∏ and a mapping f∏. If J is a subgraph of a graph G, then s∏(G, J) is true or false, and f∏(G, J) is an integer. We show the decidability of the following problem: Let Π1,...,Πn be n ISPs that fulfill our characterization and let C be a set of conditions (i, o, j) that specify two ISPs Πi and Πj and a compare symbol o ∈ {=, ≠, <, ≤, >, ≥}. Given a context-free set of graphs L defined by a HRS, is there a graph G ∈ L that has n subgraphs J1,...,Jn such that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$s_{\prod _i }$$ \end{document}(G, J) holds true for i = 1,...,n and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$s_{\prod _i }$$ \end{document}(G, Ji) o \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$s_{\prod _j }$$ \end{document}(G, Jj) for each condition (i, o, j)?