Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
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)?