http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
State complexity of basic operations on suffix-free regular languages
Han, Y.S.,Salomaa, K. North-Holland Pub. Co ; Elsevier Science Ltd 2009 Theoretical computer science Vol.410 No.27
We investigate the state complexity of basic operations for suffix-free regular languages. The state complexity of an operation for regular languages is the number of states that are necessary and sufficient in the worst-case for the minimal deterministic finite-state automaton that accepts the language obtained from the operation. We establish the precise state complexity of catenation, Kleene star, reversal and the Boolean operations for suffix-free regular languages.
Nondeterministic state complexity of nested word automata
Han, Y.S.,Salomaa, K. North-Holland Pub. Co ; Elsevier Science Ltd 2009 Theoretical computer science Vol.410 No.30
We study the nondeterministic state complexity of Boolean operations on regular languages of nested words. For union and intersection we obtain matching upper and lower bounds. For complementation of a nondeterministic nested word automaton with n states we establish a lower bound Ω(n!) that is significantly worse than the exponential lower bound for ordinary nondeterministic finite automata (NFA). We develop techniques to prove lower bounds for the size of nondeterministic nested word automata that extend the known techniques used for NFAs.
Mechatronic Architecture Development of UX-1
Soheil Zavari,Olli Usenius,Tuomas Salomaa,Jose Villa Escusol,Arttu Heininen,Jouko Laitinen,Jussi Aaltonen,Kari T.Koskinen 제어로봇시스템학회 2017 제어로봇시스템학회 국제학술대회 논문집 Vol.2017 No.10
This paper presents novel design of underwater robot for exploring abandoned mines. The hazardous environment of such mines due to unknown hydrodynamic forces and faulty navigations, brings the need of developing a reliable system able to be controlled autonomously. This capability highly rely on the basis of low level control and mechatronic architecture of the robot which demonstrate robot potential for performing real-time operations. Following, describes rapid prototyping during development phase of the robot. Further, it investigates on mechatronic development of main controller unit, propulsion system and ballast.
Approximate matching between a context-free grammar and a finite-state automaton
Ko, S.K.,Han, Y.S.,Salomaa, K. Academic Press 2016 Information and computation Vol.247 No.-
<P>For a given context-free grammar (CFG) and a finite-state automaton (FA), we tackle the edit-distance problem the problem of computing the most similar pair of strings in the two respective languages. In particular, we consider three different gap cost models for the edit-distance that are crucial for finding a proper alignment between two bio sequences: the linear, affine and concave models. We design efficient algorithms for the edit-distance between a CFG and an FA under these gap cost models. The time complexity of our algorithm for computing the linear or affine gap distance is polynomial and the time complexity for the concave gap distance is exponential. (C) 2016 Elsevier Inc. All rights reserved.</P>
Pseudoknot-generating operation
Cho, D.J.,Han, Y.S.,Ng, T.,Salomaa, K. North-Holland Pub. Co ; Elsevier Science Ltd 2017 Theoretical computer science Vol.696 No.-
<P>A pseudoknot is a crucial intra-molecular structure formed primarily in RNA strands and closely related to important biological processes. This motivates us to define an operation that generates all pseudoknots from a given sequence and consider algorithmic and language theoretic properties of the operation. We design an efficient algorithm that decides whether or not a given string is a pseudoknot of a regular language L. Our algorithm runs in linear time if L is given by a deterministic finite automaton. We study closure and decision properties of the pseudoknot-generating operation. For DNA encoding applications, pseudoknot structures are undesirable. We give polynomial-time algorithms that check whether or not a regular language L contains a pseudoknot or a pseudoknot generated by some string of L. Furthermore, we show that the corresponding questions for context-free languages are undecidable. (C) 2017. Elsevier B.V. All rights reserved.</P>
State complexity of permutation on finite languages over a binary alphabet
Cho, D.J.,Goc, D.,Han, Y.S.,Ko, S.K.,Palioudakis, A.,Salomaa, K. North-Holland Pub. Co ; Elsevier Science Ltd 2017 Theoretical computer science Vol.682 No.-
<P>The set of all strings Parikh equivalent to a string in a language L is called the permutation of L. The permutation of a finite n-state DFA (deterministic finite automaton) language over a binary alphabet can be recognized by a DFA with n(2)-n+2/2 states. We show that if the language consists of equal length binary strings the bound can be improved to f(n) = n(2)-n+1/3 and for every n congruent to I modulo 3 there exists an n-state DFA A recognizing a set of equal length strings such that the minimal DFA for the permutation of L(A) needs f (n) states. (C) 2017 Elsevier B.V. All rights reserved.</P>