Title :
A Polynomial-Time Algorithm for Checking the Equivalence for Real-Time Deterministic Restricted One-Counter Transducers Which Accept by Final State
Author :
Wakatsuki, Mitsuo ; Tomita, Etsuji ; Nishino, Takanori
Author_Institution :
Grad. Sch. of Inf. & Eng., Univ. of Electro-Commun., Chofu, Japan
Abstract :
This paper is concerned with a subclass of deterministic pushdown transducers, called deterministic restricted one-counter transducers (droct´s), and studies the equivalence problem for real-time droct´s which accept by final state. After providing some properties of these droct´s, we present a polynomial-time algorithm for checking the equivalence for these droct´s.
Keywords :
computational complexity; deterministic automata; formal verification; pushdown automata; deterministic pushdown transducers; equivalence checking; equivalence problem; final state; polynomial-time algorithm; real-time deterministic restricted one-counter transducers; real-time droct; Automata; Educational institutions; Equations; Informatics; Learning automata; Real-time systems; Transducers; deterministic pushdown transducer; deterministic restricted one-counter transducer; equivalence problem; formal language theory; polynomial-time algorithm;
Conference_Titel :
Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD), 2013 14th ACIS International Conference on
Conference_Location :
Honolulu, HI
DOI :
10.1109/SNPD.2013.18
