Search

The purpose of the article is to present the results of a study on the possibility of using a deductive approach in the study of programming languages (from the theory of formal languages to specific programming languages) and the development of a training system for implementing this approach. The issue of training specialists in the field of information technology is still relevant, and the variety of programming languages is so great that it is not always possible to guess which of them will be in demand in professional activities. According to the authors, the application of this approach will allow you to see common elements and find syntactic differences in programming languages, and therefore simplify and speed up their development. The article analyzes the methods of teaching programming, substantiates the relevance of learning formal languages by future IT specialists, formulates the requirements for a software tool to support learning formal languages, describes its implementation. Materials and methods. Theory of formal languages, syntax and semantics of programming languages, lexical analysis, analysis of various sources of information on the subject under study, systematization of the collected data, technologies for designing, implementing and testing software products, experimental research. Results. A methodology for learning programming languages through formal languages is proposed. A software training system has been created that allows you to link the theory of formal languages with high-level languages through appropriate examples. The algorithm of checking the correctness of the task execution by means of syntactic analysis of the program entered by the student and imitation of its execution is developed and implemented in the specified system. Experiments have shown the feasibility of the approach and the performance of the software product. Currently, the developed system is used at Vologda State University when teaching the disciplines “Theory of programming languages and translation methods” and “Theory of automata and formal languages”. Conclusion. The results of the study show the acceptability of the proposed approach and the expediency of using the developed program when learning programming languages.

This paper presents the framework for the creation of various domain-specific languages for verification of the functional requirements. When it comes to Requirement Engineering and the process of Validation and Verification of the requirements, there are plenty of tools for modeling, analyzing, and validating the requirements. It comes as a full-blown set of applications for validation of the requirements. But the set of the verification tools is either too complex or usable in a narrow domain. From the customers' point of view, there is a need for another independent requirement verification. This tool enables the creation of the custom verification in a way that allows users (either clients or developers) to verify requirements. It follows the IEEE guides, standards, and best practices to check all aspects of the software requirements that are neither implemented nor checked by the validation process: correctness, completeness, traceability, dependency, importance, and uniqueness. Tool implements design patterns specific to the verification process, thus enabling the faster implementation of the language. The concept can be used for development of the verification-specific language with any type of requirement representation, which will be shown by a few examples.

Technological advances and increasing customer need for highly customized products have triggered a fourth industrial revolution. A digital revolution in the manufacturing industry is enforced by introducing smart devices and knowledge bases to form intelligent manufacturing information systems. One of the goals of the digital revolution is to allow flexibility of smart factories by automating shop floor changes based on the changes in input production processes and ordered products. In order to make this possible, a formal language to describe production processes is needed, together with a code generator for its models and an engine to execute the code on smart devices. Existing process modeling languages are not usually tailored to model production processes, especially if models are needed for automatic code generation. In this paper we propose a research on Industry 4.0 manufacturing using a Domain-Specific Modeling Language (DSML) within a Model-Driven Software Development (MDSD) approach to model production processes. The models would be used to generate instructions to smart devices and human workers, and gather a feedback from them during the process execution. A pilot comparative analysis of three modeling languages that are commonly used for process modeling is given with the goal of identifying supported modeling concepts, good practices and usage patterns.

We develop a theory of vector spaces spanned by orbit-finite sets. Using this theory, we give a decision procedure for equivalence of weighted register automata, which are the common generalization of weighted automata and register automata for infinite alphabets. The algorithm runs in exponential time, and in polynomial time for a fixed number of registers. As a special case, we can decide, with the same complexity, language equivalence for unambiguous register automata, which improves previous results in three ways: (a) we allow for order comparisons on atoms, and not just equality; (b) the complexity is exponentially better; and (c) we allow automata with guessing.

In this paper we consider the problem of cycle-free context-free grammars equivalence. To every context-free grammar there corresponds a system of formal equations. Formally applying the iteration method to this system we obtain the grammar axiom in the form of a formal power series composed of the words generated by the grammar ”multiplied” by the respective ambiguities. We define a transform that attributes a matrix meaning to the system of formal equations and to formal power series: terminal symbols are substituted by matrices and formal sum and product are substituted by the matrix ones. In order to effectively compute the sum of a matrix series we numerically solve the system of matrix equations. We prove distinguishability theorems showing that if two formal power series generated by cycle-free context-free grammars are different, then there exists a matrix substitution such that the sums of the respective matrix series are different. Based on this result, we suggest a procedure that can resolve the problem of equivalence of cycle-free context-free grammars in many practical cases. The results obtained in this paper form a theoretical basis for algorithms oriented to automatic assessment of students’ answers in computer science. We present the respective algorithms. Then we compare our approach with a simple heuristic method based on CYK algorithm and discuss the limitations of our method., Fundação para a Ciência e a Tecnologia (UID/CEC/00319/2013)

This paper analyses simulation systems for teaching compilers, represents their technical characteristics and topics addressed, their benefits in the teaching process, and the advantages and disadvantages of each simulator analyzed. Based on this information, a reader can easily decide which simulator is the most suitable for his needs. The usage of simulators in education has been recognized as an effective tool for exploration of complex and dynamic systems. A simulator can illustrate a large number of abstract theoretical concepts from the various phases of program translation. Simulation systems in the field of compilers stand for a perfect combination of theory and practical experiences, and as such contribute to the improvement of the teaching process.

[EN] In this work, we analyze the computational power of Watson-Crick finite automata (WKFA) if some restrictions over the transition function in the model are imposed. We consider that the restrictions imposed refer to the maximum length difference between the two input strands which is called the delay. We prove that the language class accepted by WKFA with such restrictions is a proper subclass of the languages accepted by arbitrary WKFA in general. In addition, we initiate the study of the language classes characterized by WKFAs with bounded delays. We prove some of the results by means of various relationships between WKFA and sticker systems., This work has been developed with the financial support of the European Union's Horizon 2020 research and innovation programme under grant agreement No. 952215 corresponding to the TAILOR project.

In the inter-domain routing infrastructure, a route leak is defined as a violation of the routing policy agreed between two Autonomous Systems (AS). Route leaks have resulted in large-scale outages on the Internet, taking down several services. Although route leaks seem a simple problem, the solution is complex because: (i) ASes consider -partially- routing policy private, (ii) lack of a formal and standard language to express routing policy and (iii) BGP lacks adequate cryptographic-based security. In this paper, we present an experimental analysis of a distributed ledger-based architecture that provides a solution to route leaks. Specifically, the routing policy is unambiguously expressed using a formal language, that is then stored in a blockchain. This decentralized architecture allows private policies and interfaces seamlessly with the current BGP infrastructure, requiring no changes to routers. We build a prototype to evaluate our proposed architecture using Hyperledger, we analyze its performance using a real-world BGP dataset. Our results show that our architecture scales linearly with relevant metrics. Additionally, we validate the architecture preventing an artificially introduced route leak in a realistic 10 AS topology. This work was supported by the Spanish MINECO under contract TEC2017-90034-C2-1-R (ALLIANCE) and the Catalan Institution for Research and Advanced Studies (ICREA).

The various branches of Mathematics are not separated between themselves. On the contrary, they interact and extend into each other’s sometimes seemingly different and unrelated areas and help them advance. In this sense, the Hypercompositional Algebra’s path has crossed, among others, with the paths of the theory of Formal Languages, Automata and Geometry. This paper presents the course of development from the hypergroup, as it was initially defined in 1934 by F. Marty to the hypergroups which are endowed with more axioms and allow the proof of Theorems and Propositions that generalize Kleen’s Theorem, determine the order and the grade of the states of an automaton, minimize it and describe its operation. The same hypergroups lie underneath Geometry and they produce results which give as Corollaries well known named Theorems in Geometry, like Helly’s Theorem, Kakutani’s Lemma, Stone’s Theorem, Radon’s Theorem, Caratheodory’s Theorem and Steinitz’s Theorem. This paper also highlights the close relationship between the hyperfields and the hypermodules to geometries, like projective geometries and spherical geometries.

The collection and processing of personal data offers great opportunities for technological advances, but the accumulation of vast amounts of personal data also increases the risk of misuse for malicious intentions, especially in health care. Therefore, personal data are legally protected, e.g., by the European General Data Protection Regulation (GDPR), which states that individuals must be transparently informed and have the right to take control over the processing of their personal data. In real applications privacy policies are used to fulfill these requirements which can be negotiated via user interfaces. The literature proposes privacy languages as an electronic format for privacy policies while the users privacy preferences are represented by preference languages. However, this is only the beginning of the personal data life-cycle, which also includes the processing of personal data and its transfer to various stakeholders. In this work we define a personal privacy workflow, considering the negotiation of privacy policies, privacy-preserving processing and secondary use of personal data, in context of health care data processing to survey applicable Privacy Enhancing Technologies (PETs) to ensure the individuals&rsquo, privacy. Based on a broad literature review we identify open research questions for each step of the workflow.

The foundational features of multi-agent systems are communication and interaction with other agents. To achieve these features, agents have to transfer messages in the predefined format and semantics. The communication among these agents takes place with the help of ACL (Agent Communication Language). ACL is a predefined language for communication among agents that has been standardised by the FIPA (Foundation for Intelligent Physical Agent). FIPA-ACL defines different performatives for communication among the agents. These performatives are generic, and it becomes computationally expensive to use them for a specific domain like e-commerce. These performatives do not define the exact meaning of communication for any specific domain like e-commerce. In the present research, we introduced new performatives specifically for e-commerce domain. Our designed performatives are based on FIPA-ACL so that they can still support communication within diverse agent platforms. The proposed performatives are helpful in modelling e-commerce negotiation protocol applications using the paradigm of multi-agent systems for efficient communication. For exact semantic interpretation of the proposed performatives, we also performed formal modelling of these performatives using BNF. The primary objective of our research was to provide the negotiation facility to agents, working in an e-commerce domain, in a succinct way to reduce the number of negotiation messages, time consumption and network overhead on the platform. We used an e-commerce based bidding case study among agents to demonstrate the efficiency of our approach. The results showed that there was a lot of reduction in total time required for the bidding process.

Parsing is a key task in computer science, with applications in compilers, natural language processing, syntactic pattern matching, and formal language theory. With the recent development of deep learning techniques, several artificial intelligence applications, especially in natural language processing, have combined traditional parsing methods with neural networks to drive the search in the parsing space, resulting in hybrid architectures using both symbolic and distributed representations. In this article, we show that existing symbolic parsing algorithms for context-free languages can cross the border and be entirely formulated over distributed representations. To this end, we introduce a version of the traditional Cocke&ndash, Younger&ndash, Kasami (CYK) algorithm, called distributed (D)-CYK, which is entirely defined over distributed representations. D-CYK uses matrix multiplication on real number matrices of a size independent of the length of the input string. These operations are compatible with recurrent neural networks. Preliminary experiments show that D-CYK approximates the original CYK algorithm. By showing that CYK can be entirely performed on distributed representations, we open the way to the definition of recurrent layer neural networks that can process general context-free languages.

In this paper, we address the problem of inducing (weighted) context-free grammar (WCFG) on data given. The induction is performed by using a new model of grammatical inference, i.e., weighted Grammar-based Classifier System (wGCS). wGCS derives from learning classifier systems and searches grammar structure using a genetic algorithm and covering. Weights of rules are estimated by using a novelty Inside-Outside Contrastive Estimation algorithm. The proposed method employs direct negative evidence and learns WCFG both form positive and negative samples. Results of experiments on three synthetic context-free languages show that wGCS is competitive with other statistical-based method for unsupervised CFG learning.

Alvis is a formal modeling language intended for developing systems consisting of concurrently operating units (real-time, embedded, and distributed systems). This paper describes the timed version of Alvis that is suitable for modeling discrete-time systems. This paper is the first relatively complete description of timed Alvis. We present formal definition and semantics of timed models and the algorithm of labeled transition system generation and introduce the computer software that we developed to support Alvis. All concepts are illustrated by examples.

Nonconstructive computations by various types of machines and automata have been considered by, for example, Karp and Lipton as well as Freivalds. They allow to regard more complicated algorithms from the viewpoint of much more primitive computational devices. The amount of nonconstructivity is a quantitative characterization of the distance between types of computational devices with respect to solving a specific problem. This paper studies the amount of nonconstructivity needed to learn classes of formal languages. Different learning types are compared with respect to the amount of nonconstructivity needed to learn indexable classes and recursively enumerable classes, respectively, of formal languages from positive data. Matching upper and lower bounds for the amount of nonconstructivity needed are shown. (C) 2020 Elsevier Inc. All rights reserved.