Lin - NLC_k 변형들 : 분리와 복잡도 = Lin - NLC_k Variations : Separation and Complexity
저자
발행기관
학술지명
권호사항
발행연도
1997
작성언어
Korean
KDC
569
등재정보
구)KCI등재(통합)
자료형태
학술저널
발행기관 URL
수록면
961-969(9쪽)
제공처
본 논문에서는 선형 NLC 그래프 문법에 전통적인 스트링 문법의 촘스키 정규화형과 유사한 제약을 가한 Lin-NLC_k 그래프 문법들의 변형들의 분리에 대한 결과와 복잡도를 기술한다. Z가 Z 그래프 문법들에 의하여 생성된 그래프群이라고 하자. 분리에 대한 결과들로는 (1) Lin-RNLC⊇ Lin-NLC (Lin-RNLC₂)와 Lin-NLC₂⊆ Lin-NLC (Lin-RNLC₂), (NLC = RNLC [11]이고 Lin-eNCE₂ = Lin-eNCE [9]이라고 알려져있다.) (2) B-NLC_k ⊇A-NLC(Lin-NLC_k)와 Lin-A-NLC_k⊆A-NLC(Lin-NLC_k), (3) Lin-A-NLC_k⊆derivation-bounded A-NLC_k, 그리고 (4) Lin-e₁NCE_k⊇ Lin-NCE_k임을 보인다. Lin-eNCE 문법들의 멤버쉽 복잡도로는 각 Lin-eNCE 문법 G 와 각 k≥0에 대하여, L_(bip(k))(G)가 L(G)에 속한 이분그래프 X이며 X를 정의하는 두 이산그래프들 중 하나가 최대로 k개의 노드를 갖는 모든 그래프들의 집합일 때, L_(bip(k))(G)가 NSPACE( log n)에 있으며 L(G)안에 있는 모든 이산그래프들과 완전그래프들이 DSPACE( log n)에 있음을 보인다. 문헌에서 나타난 그래프 언어들의 효과적인 인식 알고리즘들은 대부분 분지수가 제한되어 있거나 연결된 그래프들을 위한 것이다. 위의 log-space로 인식 가능한 클래스들은 분지수가 제한되어 있지 않으며 연결되어 있지 않은 그래프들을 포함하고 있다.
더보기We present several separation results and membership complexity for Lin-NLC_k variations: Lin-NLC_k graph grammars are linear NLC graph grammars on which restriction similar to the Chomsky normal form for context-free string grammars is imposed. Let Z denote the family of languages generated by Z grammars. We show that (1) Lin-RNLC⊇ Lin-NLC (Lin-RNLC₂) and Lin-NLC₂⊆ Lin-NLC (Lin-RNLC₂), (It is known that NLC = RNLC [11] and Lin-eNCE₂ = Lin-eNCE[9].) (2) B-NLC_k ⊇A-NLC (Lin-NLC_k) and, Lin-A-NLC_k⊆A-NLC( Lin-NLC_k), (3) Lin-A-NLC_k⊆derivation-bounded A-NLC_k, and (4) Lin-e₁NCE_k⊇ Lin-NCE_k. For membership complexity of Lin-eNCE grammars, we show that for each Lin-eNCE grammar G and each k≥0, L_(bip(k))(G) ∈ NSPACE( log n), where L_(bip(k))(G) is the set of all bipartite graphs X in L(G) such that one of two discrete subgraphs defining X contains at most k nodes, and the set of all discrete (complete) graphs in L(G) is in DSPACE( log n). These log-space recognizable classes are not covered by other efficient recognition algorithms shown in the literature since these classes contain degree-boundedness, disconnected, and/or component-unbounded graphs.
더보기서지정보 내보내기(Export)
닫기소장기관 정보
닫기권호소장정보
닫기오류접수
닫기오류 접수 확인
닫기음성서비스 신청
닫기음성서비스 신청 확인
닫기이용약관
닫기학술연구정보서비스 이용약관 (2017년 1월 1일 ~ 현재 적용)
학술연구정보서비스(이하 RISS)는 정보주체의 자유와 권리 보호를 위해 「개인정보 보호법」 및 관계 법령이 정한 바를 준수하여, 적법하게 개인정보를 처리하고 안전하게 관리하고 있습니다. 이에 「개인정보 보호법」 제30조에 따라 정보주체에게 개인정보 처리에 관한 절차 및 기준을 안내하고, 이와 관련한 고충을 신속하고 원활하게 처리할 수 있도록 하기 위하여 다음과 같이 개인정보 처리방침을 수립·공개합니다.
주요 개인정보 처리 표시(라벨링)
목 차
3년
또는 회원탈퇴시까지5년
(「전자상거래 등에서의 소비자보호에 관한3년
(「전자상거래 등에서의 소비자보호에 관한2년
이상(개인정보보호위원회 : 개인정보의 안전성 확보조치 기준)개인정보파일의 명칭 | 운영근거 / 처리목적 | 개인정보파일에 기록되는 개인정보의 항목 | 보유기간 | |
---|---|---|---|---|
학술연구정보서비스 이용자 가입정보 파일 | 한국교육학술정보원법 | 필수 | ID, 비밀번호, 성명, 생년월일, 신분(직업구분), 이메일, 소속분야, 웹진메일 수신동의 여부 | 3년 또는 탈퇴시 |
선택 | 소속기관명, 소속도서관명, 학과/부서명, 학번/직원번호, 휴대전화, 주소 |
구분 | 담당자 | 연락처 |
---|---|---|
KERIS 개인정보 보호책임자 | 정보보호본부 김태우 | - 이메일 : lsy@keris.or.kr - 전화번호 : 053-714-0439 - 팩스번호 : 053-714-0195 |
KERIS 개인정보 보호담당자 | 개인정보보호부 이상엽 | |
RISS 개인정보 보호책임자 | 대학학술본부 장금연 | - 이메일 : giltizen@keris.or.kr - 전화번호 : 053-714-0149 - 팩스번호 : 053-714-0194 |
RISS 개인정보 보호담당자 | 학술진흥부 길원진 |
자동로그아웃 안내
닫기인증오류 안내
닫기귀하께서는 휴면계정 전환 후 1년동안 회원정보 수집 및 이용에 대한
재동의를 하지 않으신 관계로 개인정보가 삭제되었습니다.
(참조 : RISS 이용약관 및 개인정보처리방침)
신규회원으로 가입하여 이용 부탁 드리며, 추가 문의는 고객센터로 연락 바랍니다.
- 기존 아이디 재사용 불가
휴면계정 안내
RISS는 [표준개인정보 보호지침]에 따라 2년을 주기로 개인정보 수집·이용에 관하여 (재)동의를 받고 있으며, (재)동의를 하지 않을 경우, 휴면계정으로 전환됩니다.
(※ 휴면계정은 원문이용 및 복사/대출 서비스를 이용할 수 없습니다.)
휴면계정으로 전환된 후 1년간 회원정보 수집·이용에 대한 재동의를 하지 않을 경우, RISS에서 자동탈퇴 및 개인정보가 삭제처리 됩니다.
고객센터 1599-3122
ARS번호+1번(회원가입 및 정보수정)