TAAC'2011, Section One: Informatics and computer science

We consider right infinite words and introduce word merging transformation. We show that by merging direct sum of two periodic words with periodic word, periodic word is obtained, but by merging direct sum of bi-ideal and periodic word with periodic word, bi-ideal is obtained.

This thesis analyses finite generated biideals from given generating tuples — $(u_{0},\ldots,u_{m-1})$ and $(u_{0}',\ldots,u_{n-1}')$, investigating the case when all words $u_{i}$ are of equal length, whereas all words $u_{j}'$ are also of equal, but different length than $u_{i}$. In case, when these tuples generate the same biideal and greatest common divisor between strength of generating words are 1, this biideal is periodic. Moreover, it can be proved, that this period is equal to greatest common divisor between length of generating words.

In this paper I have tried to explain how to solve the problems in modal logic and how it can be solved by use of epistemic logic. I have explained and shown the common analogy of the epistemic logic use in possible statements of the given issue. I have analyzed a theoretical problem of muddy children and described how the solution should be found.

This paper is devoted to the transparent parallelizing technology and describes the problems that arise while implementing a cluster computing framework based on this technology. These problems are discussed and possible approaches for solving them are given. Architecture of such framework is shown and functionality of its parts is described. Efficiency of the implemented framework is shown by parallelizing a sample problem and running tests on a cluster of 1, 2, 3, 5 and 10 computers.

With the rapid growth of the information age, electronic activities of many kinds are becoming more common. The need for protection and security of information has never been greater. The conventional approach to security enforces a system-wide policy, but this approach will not work for open information systems where entirely new security issues and concerns are emerging. We argue that a new model is needed that would allow strict definition of security and measurements of its indicators to achieve the degree of security required.

In this paper we attempt to solve the problem of fine tuning Particle Swarm Optimizer parameters when training Artificial Neural Networks. An experiment for this purpose is described involving several real-world data sets. Results are presented in an easy to understand visual format. Results can be used to simplify Particle Swarm Optimization algorithm when optimizing Multilayer-Perceptron cost function surfaces.

The beginning of the twenty-first century has been characterized by an explosion of biological information. The avalanche of data grows daily and arises as a consequence of advances in th fields of molecular biology and genomics and proteomics. The challenge for nowadays biologist lies in the de-codification of this huge and complex data, in order to achieve a better understanding of how our genes shape, how our genome evolved, how we function and who we are. Bioinformatics is the application of information technology and computer science to biological problems, in particular to issues involving genetic sequences. Algorithms are centrally important in bioinformatics for dealing with sequence information.

While closure properties of some classes of right infinite words have been studied extensively, we are interested in the general algebraic structure of right infinite words. We show that partial ordering of right infinite words can be introduced with regards to whether an right infinite word can be transformed into another by a finite-state transducer.

Finding invariants subtask such as finding conditions basis is solved by using a minimization algorithm for finite acyclic automata. Conditions are interpreted as acyclic automata with one finite state after an arrangement of conditions and composition of assignment operators. Linear algorithm complexity is shown. The algorithm is implemented constructing lexical tree in Java using ANTLR Parser Generator.

This paper deals with the importance of Natural Language Toolkit for the course of Computational Linguistics, its advantages and disadvantages for students. Peculiarities of Python programming language, used in Natural Language Toolkit, are described. The specific experience of studying Natural Language Toolkit in the course of Computational Linguistics is considered. The main areas of research in Computational Linguistics students can start working on while studying are reviewed.

In this paper, we consider a problem named Network Design Problems with two-edges matching failures (NDP2EM). In a graph, any two non-incident edges is a two-edges matching. We ask for a minimum cost subgraph that contains at least one path between any pair of terminal nodes after deleting any two-edges matchings from the graph. We develop a formulation of the NDP2EM and show that how one can effectively compute the lower bound for the problem.

This paper describes an Application Programming Interface (API) for creating Resource Description Framework (RDF) triples. It proposes a specification in a general, programming language independent way to manage RDF data. This paper defines interfaces, methods and attributes using Interface Definition Language (IDL). The programming interfaces provide a statement-centric approach. This new API is developed in response to a demand from a wide range of users, who want create, update and delete RDF statements.

This article comes to present a formalization of a security problem: validating a message sent from an uncertain source — particularly halting DDoS attack.

Were made first steps in drafting the programs factory that can serve as informational and educational internet project in the field of software engineering. Main objective is to develop a certified software and scientific artifacts exchange system for KNU students to improve their skills and quality, reliability of their systems and products.

In this paper we describe high-performance implementations of SSA method for gas consumption time series analysis. We propose implementation for distributed-memory systems and associated grid application. Proposed results were used in online monitoring system of the municipal gas distributing station.

The analysis of software production industry stage is analyzed. Base components of scientific software are proposed. Their content and role in researches are motivated. New software and computer science education oriented disciplines are formulated.

This paper considers principles of dynamic (adaptive) information security resource management, which aims to achieve optimal size of information security investment and timing for investment. Adaptive approach implies protection that is changed according to attacker's actions. It is generally known that successful attack only leads to negative consequences and great losses. For certain options and conditions attacker's actions can be used for our adventage by determining after attack weakest links of protection and thus be able to adjust it, knowing the degree of vulnerability. Paper describe an example in which results of previous distribution and resource implementation after attack are compared. The current research presents conditions under which it is expedient to use adaptive management and situations when this approach give the best results.

The acceleration of calculations in the multistart method for finding solutions of systems of nonlinear equations by paralleling technology programs for MPI and CUDA was investigated. The are several graphic accelerators were involved ath the same time and their times was compared with the same software code for only MPI nodes. Numerical experiments were conducted on two clusters with different configuration of graphics accelerators. Tthe impact of configurations on computational results was studied.

The method of information security system choosing for enterprise communication networks by the survivability criterion under uncertainty destabilizing factors influences was developed.

Multiset table algebra is constructed. The notion of a table specified using the notion of multiset, each table correlated to a certain scheme. The basic operations over tables are defined. The basis of the resultant table and the number of duplicates of each tuple are defined for each operation too.

This paper discusses the main ways of testing Web-applications both manual and automated. In particular, we consider some theoretical aspects of manual testing, and the main means of automated testing. The study of automated testing was made on the example of concrete Web-applications.

The possibilities and features of the implementation of artificial intelligence in computer games are overlooked in this paper. We propose to use fuzzy sets with a list of specific situations of their use. Basic artificial intelligence computer games constantly require improvements to meet the growing demands of all players. This article discusses how intelligent agents and fuzzy logic can help improve the quality and quantity of the most important elements of computer games: cooperation. Application of fuzzy logic in the design details of behavior is illustrated by the examples of simple game.

The system analyzes a relational database without using the administration resources. The analysis is automatic. Also, it makes the choice of information required for an analyst, creates and optimizes a multidimensional analytical framework. The project provide quick and convenient access to the analytical framework for anyone not familiar with the system. The access is provided through a Web-based interface or the client application.

The problem of text analysis in natural language. We consider the morphemic analysis of words of text as the first stage analysis. A general parsing algorithm and a brief description of the required linguistic rules. A comparison with existing technologies.

This paper is dedicated to the problem of automatic construction network SDL-specification models of distributed systems. Language of specification and descriptions SDL adopted as an international standard. Considered SDL-systems with a timer, means of preserving the signal and priorities, that allow to introduce a significant class of communication protocols. Colored Petri Nets selected as models, that extend through the semantics of time and priorities. The paper describes method of translating SDL-systems in this network model.

In work the question of the automated analysis of quality of the object-oriented applied program systems is considered. The analysis is based on the software metrics theory and complex estimation of quality of created program system.

Article describes applying of different optimal configuration search algorithms to parallel algorithm of short-term weather conditions forecast problem solving. Results are basis for stand-alone generic application creation which efficiently performs this search on target platform in fully automated mode.

The article explores the problem of defining the term ``subject'' and ``information object''. Also describes a technique for automating the process of defining themes. Described the evaluation of the results obtained by applying the approach in practice. We give examples of software systems for the control of information.

Different definitions of concept of process are analyzed. Correspondence between transition systems and definitions of process on different levels of abstraction is shown. The most important equivalence relations on states of attributed transition systems are considered. Among them bisimilarity and trace equivalence. Special algebras are constructed. Correspondence between elements of algebras and classes of equivalence is proved. It is further possible to consider labels of states of transition system to be nominative data, what will lead to new results.

Two productivity measures of information security – regarding vulnerability reduction and treat reduction are considered. Measures of these two productivity form two-dimension space, which can be divided into zones which determine the different strategy of optimal allocation of investment. An example that demonstrates the technique for determining the boundaries of zones is set. The conditions which should use the methods are analyzed.

We are considering different approaches to the summation of the multiplicative functions and proposing an algorithm to calculate $\sum_{n\le x} f(x)$ faster then for $O(x)$ operations, if $f$ is a Dirichlet convolution of the fast summable functions. Such algorithms are very useful in the experimental testing of the asymptotic hypothesis in the number theory.

The problem of constructing the hardware and software set-up for autonomous robofootball by the rules of RoboCup Small Size League is considered. Problems of pattern recognition in video under various lighting condition, optimal robots trajectories determination, stable motion along the trajectory, automatic collision avoidance were solved. The set-up is designed for the realization using low-priced hardware base. Transparent implementation allows to use it even when working with schoolchildren and junior students.

This paper introduces the information system for calculating of the basic parameters necessary for determining the rates for short-term and long-term life insurance. The structure of the system which is developed and implemented as a final software product. With the help of the developed information system, we have calculated the tariff rates for different initial conditions, which allowed to obtain quickly and accurately the reliable data in the process of contracts conclusion for life insurance.

The purpose of this study is to develop a method guaranteed-detected Disarmament Affairs 4 multiple errors by using the minimum number of control- discharges.

The problems of the long-term preservation of the archival electronic documents (AED) are considered. The main requirements for the portion of the program tests in the composition of the AED test bench are detailed. The application implementation architecture of the test bench is proposed. The impossibility of achieving the interoperability without the specification of the program tests on the basis of the normative documents, namely, the harmonized standards, are motivated.

This paper considers non-relational database management systems (NoSQL). The need for separation from traditional RDBMS is caused by limitation in the structure of data stored. Unlike RDBMS, NoSQL solutions allow for individual records using an arbitrary structure and arbitrary fields. Another significant factor is the possibility to linearly scale the database to any number of system units when scaling traditional RDBMS becomes ineffective even at ten knots. NoSQL extremely promising for distributed data warehouses and cloud.

Solved the problem of defining the parameters (size of blocks and index entries of the file) of the optimal index-sequential database files organization stored in external memory of multiprocessor computers, in the case of parallel search for various laws of probability distribution access to records. By optimality criterion adopted the general expectation of time needed for searching in the file.

Discusses some algorithms for computing the patterns in DNA sequences. Provides a possible biological interpretation of the results.

In the paper the problem of proximity, namely the construction of a minimal skeleton tree for a given set of points, and a new algorithm to solve this problem based approach "divide and conquer". The algorithm has time complexity estimate O(N log N) and uses O(N) memory.

Parallel realization of method of conjugate gradients for solving systems of linear algebraic equations (SLAE) with sparse matrix of irregular structure is considered. Much attention is paid to a way of building matrix regularizer, where method of parallel sections is used. An appropriate program for solving SLAE using MIMD-computers was created. Time dependences on matrix parameters and processes amount were obtained.

The hypothetical model of the possible reception of the electromagnetic radiation with the dynamic quasi fractal water formations existing in the biological organisms was suggested.

In the article are examined the various ways to describe the uncertain variable, namely: probabilistic presented by random variable; possibilistic presented by fuzzy variable and mixed presented by fuzzy random variables. Also here are proposed some examples of problems in which you can see the basic similarities and differences ways of description.

In this paper we study properties of an algebra of languages that can be represented by vertex-labeled graphs and Kleene algebra of regular languages, and establish some new relationships between these algebraic structures. Our main results are as follows: - it is proved that the algebra of languages that can be represented by vertex-labeled graphs represents the same class of languages as Kleene algebra of regular languages without empty word; - we show that these algebras have isomorphic sub algebras; - we give а constructions that makes it possible to transform regular expression of Kleene algebra into a regular expression of algebra of languages that can be represented by vertex-labeled graphs without changing its language.

It is resolved the problem of analysis of complexity of identification (parametric one as well as of initial state) for quite simple non-linear one-dimensional reversible automata with delay 2 over any finite commutative-associative ring with unit.

The new algorithm of recognition of chess maze by means of moving on him an agent is offered in paper. The agent walks around the maze on an external contour and makes expression in elementary motions, describing the external contour of the maze. Further the formula of labyrinth as a structure of rectangles is made. Such approach reduces complication of recognition of chess mazes.

A graph exploration problem by three agents is considered. Two agents-researchers simultaneously move on unknown graph, they read and change marks of graph elements, transfer the information to the agent-experimenter. It builds explored graph representation. An algorithm is proposed which recognizes any finite non-oriented graph. For graph exploration each agent needs two different marks (in total three colors), quadratic (from amount of nodes of the graph) memory and quadratic number of steps.

The report covers the main stages of constructing a control model of the parallel computational process branching problem in time, is an example of temporal model of a parallel process to the management of a tree of the original C-program. Outlined in the results allow us to consider the application of the specification of the parallel implementation of algorithms that take into account the temporal characteristics of operations and system requirements for the temporal characteristics of program execution.

The traditional approach to software development uses sequential algorithms. Popular integrated development environments and SDK toolchains (Visual Studio, XCode, .Net, Cocoa, QT, java) are orient to single-threaded code by default. The new approach of async communication is suggested that uses messages, priority queues and worker threads as the mean of solving problems that single-threaded programs typically have. The suggested approach is implemented as a .Net library.

Machine readable zone (MRZ) is present on every modern passport of most countries in the world and on Ukrainian foreign passports. It's two alpha-digital rows, where basic owner's information is duplicated for machine readability purpose. In this work a method for MRZ extraction and recognition is proposed and a realization valid for mobile applications is presented.

Definitions of orthogonality of different arity operations and orthogonality of different dimention hypercubes as well as their relationship are given. They differ from the known. A connection between composition and orthogonality is stated and a criterion of orthogonality for linear quasigroups is found.

The problem of minimizing oriented deterministic graphs with distinguished vertices. Identified a number of classes of graphs for which the minimization is performed in fewer steps than the classical algorithm. We consider graphs consisting of one component of a strong connection. The algorithms of time complexity O(e), e — the number of arcs. Correctness and convergence of the algorithms are proved.

This paper describes a new parallel block algorithm for solving linear algebraic systems with non-degenerate matrices for hybrid systems that combine MIMD- and SIMD-architecture, ie calculation on multicore computers with accelerating of computation on graphics processors. Presented the result of solving problems on the pilot sample of hybrid system Inpargraf, which developed in the V.M. Glushkov Institute of Cybernetics of NAS of Ukraine and the State scientific production association "Electronmash". Most scientific and engineering problems are reduced to solving systems of linear algebraic equations, so the problem of creating efficient algorithms for solving them on modern element base and the use of modern technology is very relevant.