내 신청현황
종류	모집공고명	진행상태
신청내용이 없습니다.

알림마당

home

XML을 위한 오토마타 개관

전문가 제언: ○ 형식 언어 이론에서 상태(state)는 한 입력을 받아들이고 그 입력에 따라 하나의 출력과 현 상태에서 다른 상태로 전이하는 하나의 개념적 모델이다. 어떤 일을 처리하기 위하여 몇 개의 상태를 하나의 시스템으로 묶은 것을 유한상태기계라고 한다. 유한상태기계에는 상태 집합, 입출력 알파벳, 상태전이함수 및 출력함수가 포함된다. 각 상태에서 출력이 없고 전이만 있으며 최종상태가 존재하는 유한상태 기계를 오토마타라고 한다.

○ 오토마타는 일종의 추상적인 기계이다. 오토마타가 초기상태로부터 최종 인식상태에 이르는 모든 입력을 연접하여 얻어지는 스트링을 인식할 때 이 언어를 정규언어라고 한다. 한편 XML 문서는 스트링이고 XML 문서의 구조는 확장된 문맥 자유 문법으로 나타내는 정규언어이므로 XML 문서는 스트링 오토마타로 다룰 수 있다.

○ Schwentick는 이 개요에서 XML 프로세싱 문제에서 사용되는 여러 종류의 오토마타에 대한 기본 성질들을 개관하고 이 성질들이 XML 프로세싱의 네 측면인 스키마, 내비게이션, 질의 및 변환과 어떻게 연계되는 가를 탐색한다. 여기서는 XML 트리 오토마타, 순서열 트리 오토마타, 문서 오토마타 등의 여러 오토마타의 정의와 정리들이 소개되고 또 검증이나 복잡성에 대한 기존의 연구 결과들이 개관되어 XML을 위한 오토마타의 연구의 흐름과 방향을 제시하고 있다.

○ 오토마타 이론은 형식 언어의 한 분야로서 컴퓨터 언어 이론과 데이터 프로세싱 이론 및 논리와 트리 구조를 다루는 이산 계산 이론 등과 같은 컴퓨터 이론의 핵심 분야이다. 비록 실용화와 같은 가시적인 결과는 없지만 모든 언어와 프로세싱의 기초이론으로서 매우 중요한 분야이다. 컴퓨팅 환경의 진화에 따라 개발되는 여러 가지 컴퓨팅 자원의 검증과 이론의 기초를 위하여 오토마타 분야는 앞으로도 많은 진화연구가 필요할 것으로 여겨진다. 이 논문은 오토마타와 XML을 비롯하여 프로그래밍 언어, 기계어, 인공지능 등을 연구하는 분들에게 많은 참고가 되리라고 본다.

저자: Schwentick, T; AF Schwentick, Thomas
자료유형: 학술정보