Search

Supervisory Control Theory (SCT) is a powerful framework to design a controller for a Discrete Event System (DES). However, several issues appear because of the different nature of SCT and synchronous-based systems, on which a controller will be executed. While SCT, which relies on automata theory, is based on the occurrence of asynchronous events, a computer-based system is based on a synchronous digital system. Even though most of the contributions to overcome the problems derived by this fact concentrate on the usability for Programming Logic Controllers, no significant contribution has been made for embedded execution platform. If so, it relies on the hand-coded implementation of the supervisor controller. The work here proposed, combines previous research contributions to develop an embedded and distributed platform for supervisor automata model execution. No code translation is required, since the models, after simulation, can be directly executed on the proposed platform. The results obtained by two case studies show the feasibility of the conceived platform.

Link prediction is an iconic problem in complex networks because deals with the ability to predict nonobserved existing or future parts of the network structure. The impact of this prediction on real applications can be disruptive: from prediction of covert links between terrorists in their social networks to repositioning of drugs in molecular diseasome networks. Here we compare: (1) an ensemble meta-learning method (Ghasemian et al.), which uses an artificial intelligence (AI) stacking strategy to create a single meta-model from hundreds of other models; (2) a structural predictability method (SPM, Lü et al.), which relies on a theory derived from quantum mechanics and does not assume any model; (3) a modelling rule named Cannistraci-Hebb (CH, Muscoloni et al.), which relies on one brain-bioinspired model adapting to the intrinsic network structure.We conclude that brute-force stacking of algorithms by AI does not perform better than (and is often significantly outperformed by) SPM and one simple brain-bioinspired rule such as CH. This agrees with the Gödel incompleteness: stacking is optimal but incomplete, you cannot squeeze out more than what is already in your features. Hence, we should also pursue AI that resembles human-like physical ‘understanding’ of simple generalized rules associated to complexity. The future might be populated by AI that ‘steals for us the fire from Gods’, towards machine intelligence that creates new rules rather than stacking the ones already known.

International audience; This special issue contains eight articles which are based on extended abstracts that were presented at the 35th Symposium on Theoretical Aspects of Computer Science (STACS), which was held at the University of Caen from February 28th to March 3rd, 2018. These extended abstracts were chosen among the top papers of those that were selected for presentation at STACS 2018 in a highly competitive peer-review process (after which only 54 papers out of 186 submissions were accepted). Compared with the original extended abstracts, the articles have been extended with a description of the context, full proofs and additional results. They underwent a further rigorous reviewing process, following the TOCS Journal standards, completely independent from the selection process of STACS 2018. The topics of the chosen papers cover a rich set of areas within Theoretical Computer Science, that is, algorithmic game theory, automata theory, circuit complexity, efficient algorithms, logic and model checking, Markov chains, pa-rameterized complexity, and proof complexity. Kernelization (provably effective and efficient preprocessing) is a central theme in parameterized complexity. The article Computing Hitting Set Kernels by AC 0-Circuits by Max Bannach and Till Tantau presents for the first time kernels for the d-Hitting Set problem that can be computed in constant parallel time, thereby refuting a previous conjecture. To this end, the authors introduce a new, generalized notion of hypergraph sunflowers. Altogether, this gives an important contribution to parameterized circuit complexity.

The event-triggered hybrid control is proposed in this study to realise multi-model switching when the microgrid system is operating in the island mode. The hybrid control includes decentralised control strategy and coordinated control strategy. Firstly, control commands in the hybrid control strategy are triggered by the event triggering mechanism including trigger events and trigger conditions. When a trigger condition is met, the corresponding event is triggered to execute the corresponding control command. Secondly, the microgrid system is divided into an upper control layer and a lower execution layer by using the multi-agent system theory. For the upper control layer, a coordinated control strategy based on decision tree algorithm is designed, which can not only issue switching control commands to the lower execution layer, but also reduce the number of switching, improve system stability, and enrich the control strategy. For the lower execution layer, a decentralised control strategy is designed to realise distributed operation of the underlying units. Finally, the model of hybrid automata of each unit is established to ensure the smooth switching of working modes of each unit. The simulation results verify the effectiveness of the event-triggered hybrid control strategy for controlling the microgrid.

We show how some problems in additive number theory can be attacked in a novel way, using techniques from the theory of finite automata. We start by recalling the relationship between first-order logic and finite automata, and use this relationship to solve several problems involving sums of numbers defined by their base-2 and Fibonacci representations. Next, we turn to harder results. Recently, Cilleruelo, Luca, & Baxter proved, for all bases b ≥ 5, that every natural number is the sum of at most 3 natural numbers whose base-b representation is a palindrome (Cilleruelo et al., Math. Comput. 87, 3023–3055, 2018). However, the cases b = 2, 3, 4 were left unresolved. We prove that every natural number is the sum of at most 4 natural numbers whose base-2 representation is a palindrome. Here the constant 4 is optimal. We obtain similar results for bases 3 and 4, thus completely resolving the problem of palindromes as an additive basis. We consider some other variations on this problem, and prove similar results. We argue that heavily case-based proofs are a good signal that a decision procedure may help to automate the proof.

ZTP and deployment of GPU-based computing are the new terms for empowering extreme automation. With notions associated with these terms come new challenges and opportunities, as well as a dramatic shift in the landscape of programming the future collaborative manufacturing systems. We have only touched the surface of this exciting topic.

Translating computation tree logic formulas into Buchi tree automata has been proven to be an effective approach for implementing branching-time model checking. For a more generalized class of lattice-valued (L-valued, for short) computation tree logic formulas, the revelent study has not proceeded yet. We introduce the notion of L-valued alternating Buchi tree automata and achieve the goal of associating each L-valued computation tree logic formula with an L-valued Buchi tree automaton. We show that a satisfiability problem for an L-valued computation tree logic formula can be reduced to one for the language accepted by an L-valued Buchi tree automaton. L-valued alternating Buchi tree automata are the key to the automata-theoretic approach to L-valued computation tree logics, and we also study their expressive power and closure properties.

Virtual power plant (VPP) is a hybrid power system with a mesh of distributed resources, local loads and storage with both discrete and continuous variables involved. Control of such system requires advanced control schemes to make distributed assets act together to mimic an actual power plant. Previously, to study the behaviour of such systems, complex algorithms and modelling tools have been used but this paper proposes the use of Hybrid Automata (HA) as a convenient tool to model these systems. To demonstrate this, HA is used to model a VPP for a research farm owned by Newcastle University as a first step to design the control for the system.

Graph theory plays crucial role in structuring many real-world problems including, medical sciences, control theory, expert systems and network security. Product in graphs, an operation that consider two graphs and produce a new graph by simple or complex changes, has wide range of applications in games theory, automata theory, structural mechanics and networking system. An intuitionistic fuzzy model is used to handle the vagueness and uncertainty in network problems. A Pythagorean fuzzy model is a powerful tool for describing vagueness and uncertainty more accurately as compared to intuitionistic fuzzy model. The objective of this paper is to apply the concept of Pythagorean fuzzy sets to graphs and then combine two Pythagorean fuzzy graphs (PFGs) using two new graph products namely, maximal product and the residue product. This research paper investigates the regularity for these products. Moreover, it discusses some eminent properties such as strongness, connectedness and completeness. Further, it proposes some necessary and sufficient conditions for $${\mathscr {G}}_{1}*{\mathscr {G}}_{2}$$ and $${\mathscr {G}}_{1}\cdot {\mathscr {G}}_{2}$$ to be regular. Finally, decision-making problems concerning evaluation of best company for investment and alliance partner selection of a software company are solved to better understand PFGs.

This paper presents a method to use model checking techniques to verify the safety of the behavior of cooperative vehicles. We model the roadway, cooperative and non-cooperative actors as automata that are used to construct the state space of the local traffic system using techniques from automata theory. We then translate the automata into a format readable by nuXmv, a state-of-the-art model checker. Together with specifications that model accident- and deadlock-freeness, we then use nuXmv to prove that a local traffic system is safe.

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.

This paper is towards the algebraic and topological study of automata based on residuated and co-residuated lattices via different operators. The interrelationships among the operators are discussed. Interestingly, we show that the algebraic concepts of an automaton based on a residuated and co-residuated lattice can be expressed in terms of [Formula: see text]-topology/co-topology induced by operators. Finally, a composition of such automata is introduced and its categorical significance is discussed.

A refinement preorder for a model of concurrent systems should be compositional (i.e. a precongruence for parallel composition) and should not introduce faults into a fault-free specification. Arguably, if these are the features of interest, the coarsest such precongruence is the optimal refinement preorder and often, it preserves additional properties. For the model of interface automata, originally faults are communication errors in the form of unexpected inputs. The respective optimal preorder has been characterized as the inclusion of two trace sets. Here, we extend these characterizations by regarding also quiescence (quiescence and divergence resp.) as faults. The latter preorder is coarser, i.e. better, than an earlier preorder regarding errors, quiescence and divergence. A conjunction operator allows to specify different facets of an overall specification by separate automata and then to combine them. We also present conjunction operators for our settings, avoiding flaws that can be found in the literature.

Inspired by Switching Systems and Automata theory, we investigate how combinatorial analysis techniques can be performed on a hybrid automaton in order to enhance its safety or invariance analysis. We focus on the particular case of Constrained Switching Systems, that is, hybrid automata with linear dynamics and no guards. We follow two opposite approaches, each with unique benefits: First, we construct invariant sets via the ‘Reduced’ system, induced by a smaller graph which consists of the essential nodes, called the unavoidable nodes. The computational amelioration of working with a smaller, and in certain cases the minimum necessary number of nodes, is significant. Second, we exploit graph liftings, in particular the Iterated Dynamics Lift (T -Lift) and the Path-Dependent Lift (P-Lift). For the former case, we show that invariant sets can be computed in a fraction of the iterations compared to the non-lifted case, while we show how thelatter can be utilized to compute non-convex approximations of invariant sets of a controlled complexity. We also revisit well studied problems, highlighting the potential benefits of the approach. In particular, we apply our framework to (i) invariant sets computations for systems with dwell-time restrictions, (ii) fast computations of the maximal invariant set for uncertain linear systems and (iii) non-convex approximations of the minimal invariant set for arbitrary switching linear systems.

Graph learning by automata is a basic task in many applications. Among these applications are verification and testing of software and hardware systems, network exploration including Internet and GRID basing on formal models. The system or network model, in the final analysis, is a transition graph with properties to be examined. In the recent years the size of the systems and networks in everyday use and, consequently, the size of their models and graphs to be learned grows constantly. Problems arise when graph exploration by a single automaton (computer) either requires a lot of time, or a lot of computer memory, or both. Therefore, there is a task of parallel and distributed graph exploration. This task is formalized as graph learning by a set of automata (a set of computers with sufficient total memory working in parallel). This paper covers the solution of this task. First of all the behavior of the automaton on the graph is formalized. Then the algorithm of the graph learning is described in detail. The estimation of the algorithm is O ( m + nD ). Some ways of possible optimization is discussed.

For several decades, the role of computers has been appreciated in achieving various educational goals. Computer-assisted instructions become very popular in educational settings nowadays. Various intelligent tutoring systems have been developed to support learning in different contexts. This work investigates a tutoring system for learning Finite State Machines (FSM), one of the models of computation in Automata Theory, called ILSA. ILSA was deliberately developed to appeal to learners' achievement goal orientations. Achievement Goal Orientation theory suggests that learners could be mastery-oriented or performance-oriented. Hence, the specific aim of this investigation is to examine if there is evidence of alignment between system utilization and achievement goal orientations of learners. In other words, did the learners use the features of ILSA according to their respective orientation? Results showed that the goal orientations in Post-ILSA 1 have high manifestations of alignment between utilization and achievement goal orientations.

International audience; This special issue contains five articles which are based on extended abstracts presented at the 35th Symposium on Theoretical Aspects of Computer Science (STACS). The conference was held at the Technical University of Berlin from March 13 to March 16, 2019. The extended abstracts were chosen among the top papers of those which were selected for presentation in a highly competitive peer-review process (after which only 54 papers out of 260 submissions were accepted, putting it among the most competitive conferences in Theoretical Computer Science). Compared with the original conference papers, the articles have been extended with a description of the context, full proofs, and additional results. They underwent a rigorous reviewing process, following the TOCS journal standards, completely independent from the selection process of STACS 2019. The topics of the chosen papers cover various areas of Theoretical Computer Science, that is, algorithmic graph theory, automata theory, linear dynamical systems, parameterized complexity analysis, and distributed algorithms. In what follows, we briefly describe the contributions of the papers, ordered alphabetically by author names. Significantly extending the results of the conference version, the article "First-Order Orbit Queries" by Shaull Almagor, Joel Quaknine, and James Worrell studies fundamental reachability questions, so-called orbit problems: Here, for example, we are given a square matrix A of dimension d over the rationals and two semialgebraic

The intelligent system controls the subsystems of each aircraft in real time to ensure the normal development of the tasks of the aircraft system. In the process of system communication, the control system is required to strictly control the correctness of the control algorithm flow and the accuracy of the control sequence in order to ensure the safety of the aircraft system. This paper uses UPPAAL, a formal model detection tool based on time automata theory, to formally model and validate the algorithm flow of an intelligent system and a subsystem. First, the algorithm flow of the intelligent system is analyzed, and then it is formally modeled using the time automaton method. Second, the properties that need to be verified are extracted from the algorithm flow and described with the formal language BNF. Finally, the function and performance correctness are automatically verified using the UPPAAL model detection tool. The experimental results verify that the intelligent system meets the security, accessibility and activity requirements.

We introduce a new formalisation of languages, called keyboards. We consider a set of elementary operations (writing/erasing a letter, going to the right or to the left,...) and we define a keyboard as a set of finite sequences of such operations, called keys. The corresponding language is the set of words obtained by applying some sequence of those keys. Unlike classical models of computation, every key can be applied anytime. We define various classes of languages based on different sets of elementary operations, and compare their expressive powers. We also compare them to well-known classes of languages (Chomsky hierarchy). We obtain a strict hierarchy of languages, whose expressivity is orthogonal to the one of the aforementionned classical models. -- Nous introduisons une nouvelle repr\'esentation de langages, les claviers. On se munit d'un ensemble d'op\'erations \'el\'ementaires (ajout, effacement d'une lettre, d\'eplacement \`a droite, \`a gauche, ...), et on d\'efinit un clavier comme un ensemble de suites finies d'op\'erations \'el\'ementaires, appel\'ees touches. Son langage sera l'ensemble des mots obtenus en appliquant une suite quelconque de touches. Contrairement \`a des mod\`eles de calcul classiques, toutes les touches peuvent \^etre appliqu\'ees \`a tout moment. En premier lieu nous d\'efinissons diff\'erentes classes de claviers en faisant varier l'ensemble des op\'erations \'el\'ementaires autoris\'ees, et nous comparons l'expressivit\'e des classes de langages obtenues. Nous comparons \'egalement ces classes \`a la hi\'erarchie de Chomsky. Nous obtenons que toutes les classes \'etudi\'ees sont diff\'erentes, et nous caract\'erisons les classes inclues dans les rationnels et les alg\'ebriques. L'expressivit\'e des claviers semble orthogonale \`a celle des mod\`eles \'evoqu\'es pr\'ec\'edemment., Comment: Two versions, in French and in English

The main objective of our paper is to focus on the study of sequences (finite or countable) of groups and hypergroups of linear differential operators of decreasing orders. By using a suitable ordering or preordering of groups linear differential operators we construct hypercompositional structures of linear differential operators. Moreover, we construct actions of groups of differential operators on rings of polynomials of one real variable including diagrams of actions–considered as special automata. Finally, we obtain sequences of hypergroups and automata. The examples, we choose to explain our theoretical results with, fall within the theory of artificial neurons and infinite cyclic groups. Hlavním cílem článku je studium posloupností (konečných nebo spočetných) grup a hypergrup lineárních diferenciálních operátorů klesajících řádů. Za použití vhodného uspořádání nebo předuspořádání grup lineárních diferenciálních operátorů konstruujeme hyperkompoziční struktury lineárních diferenciálních operátorů. Dále konstruujeme akce grup diferenciálních operátorů na okruzích polynomů jedné proměnné, a to včetně konstrukce diagramů těchto akcí, považovaných za automaty. Konečně, v článku získáváme posloupnosti hypergrup a automatů. Příklady, na kterých ilustrujeme teoretické výsledky článku, spadají do teorie umělých neuronů a nekonečných cyklických grup.

In this dissertation we present a mathematically minded development of the correction proof of Kleene’s theorem conversion of regular expressions into finite automata, on the basis of equivalent expressive power. We formalise a functional implementation of the algorithm and prove, in full detail, the soundness of its mathematical definition, working within the Why3 framework to develop a mechanically verified implementation of the conversion algorithm. The motivation for this work is to test the feasibility of the deductive approach to the verification of software and pave the way to do similar proofs in the context of a static analysis approach to (object-oriented) programming. In particular, on the subject of behavioural types in typestate settings, whose expressiveness stands between regular and context-free languages and, therefore, can greatly benefit from mechanically certified implementations. Nesta dissertação apresentamos um desenvolvimento matemático da prova de correcção da conversão de expressões regulares em autómatos finitos do teorema de Kleene, com base no seu poder expressivo equivalente. Formalizamos uma implementação funcional do algoritmo e provamos, em detalhe, a correcção da sua definição matemática. Trabalhando no framework Why3 para desenvolver uma implementação mecanicamente certificada do algoritmo de conversão. A motivação para este trabalho é testar a viabilidade da metodologia e preparar o caminho para fazer provas semelhantes no contexto de uma abordagem de análise estática na programação (orientada para objectos). Em particular, no tópico dos tipos comportamentais com typestates, cuja expressividade está entre a das linguagens regulares e livres-de-contexto. Podendo, por isso, beneficiar enormemente de implementações mecanicamente certificadas

Train control system of traditional urban rail transit usually controls train operation according to the movement authorization generated by Zone Controller. The generation of vehicle-to-vehicle communication system makes the system of MA generation change from ZC to On-board subsystem. At the same time, the data flow in the process of generating control information is simplified, which greatly enhances the autonomy and flexibility of the train. This paper introduced the system architecture of train operation control system based on vehicle-to-vehicle communication, focused on the analysis of information exchange among subsystems and the functional requirements of MA calculation in the process of autonomous generation of MA by VBTC. The timed automata theory is used to model the generation process of MA, and the UPPAAL is used to verify the model, which proves the rationality and effectiveness of MA algorithm in vehicle-to-vehicle communication system.

Dissertation, RWTH Aachen University, 2021; Aachen : RWTH Aachen University 1 Online-Ressource : Illustrationen, Diagramme (2021). = Dissertation, RWTH Aachen University, 2021, Tree automata on infinite trees are a powerful tool that is widely used for decision procedures and synthesis of logical specifications. It is well known that finite tree automata have good algorithmic properties, but somewhat limited expressive power. For example, they cannot verify that certain subtrees of an input tree are equal. In order to model such properties, we study extensions of tree automata that use so called constraints to compare whole subtrees of an input. We distinguish between two types of constraints: local constraints and global constraints. Tree automata with local constraints were introduced in the 90s by Bogaert and Tison, who analyzed a model of tree automata on finite ranked trees that use guard terms in the transitions in order to compare sibling subtrees at each node. Recently Carayol, L��ding and Serre generalized the model to the setting of infinite trees. They proved that the class of languages recognizable by these automata is effectively closed under all Boolean operations and that the emptiness problem for parity tree automata with these local sibling constraints is decidable. In this thesis we first summarize the existing results of tree automata with local constraints for infinite trees. Then we paritally answer the open question whether the class of languages recognizable by these automata is closed under projection. That is, we show that in the case of automata with B��chi acceptance condition the class of recognizable languages is closed under projection. As a consequence, we obtain a new decision algorithm for the emptiness problem as well as a proof for the fact that each non-empty language recognized by a B��chi tree automaton with sibling constraints contains a regular tree. Moreover, we also study logical characterizations of this class of languages. Tree automata with global constraints were introduced by Filiot, Tison and Talbot in 2008. They studied tree automata on finite trees that can compare subtrees whose positions are defined by the states reached in a run. For example, this model can verify that all subtrees rooted at positions where a certain state is reached are equal. This model was then generalized by Bargu���� et. al., who showed the decidability of the emptiness problem. In this thesis we generalize the model of Bargu���� et. al. to the setting of infinite trees. We show that most closure properties and decidability results can be extended from finite to infinite trees. However, new techniques are required in order to do so. While the decidability of the emptiness problem remains an open question in general, we present decidability results for some subclasses of tree automata with global constraints. That is, if the automaton tests only for equality of subtrees (and not for inequality) the emptiness problem is decidable. The same is true if the underlying language (i.e. when ignoring the constraints) is countable. We also study the special case of automata with global constraints on unary infinite trees (��-words). Here we show that in contrast to branching trees, the class of languages recognizable by these automata is closed under complement. Finally, we present precise logical characterizations for all of the subclasses mentioned, by extensions of monadic second order logic on infinite trees (or ��-words)., Published by RWTH Aachen University, Aachen

part : TC 1: Foundations of Computer Science; International audience; Descriptional complexity has historically been a multidisciplinary area of study, with contributions from automata theory, computational complexity, cryptography, information theory, probability, statistics, pattern recognition, machine learning, computational learning theory, computer vision, neural networks, formal languages and other fields. Some basic questions are: How succinctly can a descriptional system represent objects (for example, encoded as formal languages) in comparison with other descriptional systems? What is the maximal size trade-off when changing from one system to another, and can it be achieved?

Here we give a selection of instructional examples of holonomy decompositions of finite transformation semigroups. These are edge cases that can be used in verifying computational implementations, as counterexamples in learning the holonomy method of the Krohn-Rhodes Theorem, and they are also sources of open problems.

Formaali kieli reStructuredText on laajassa käytössä Aalto-yliopistossa kehitettyä sähköistä oppimisympäristöä A+ varten kirjoitettujen tietojenkäsittelytieteiden ja matemaattisten oppimateriaalien lähdekoodina. Kyseinen kieli ei kuitenkaan tähän mennessä ole ollut kovin helposti käännettävissä korkealaatuisesti muuhun kuin HTML-muotoon. Tähän ongelmaan pyrkii vastaamaan kielen LaTeX osajoukko tai fragmentti LarST eli LaTeX to reStructuredText, joka olisi erinäisten kääntäjien kautta käännettävissä eri esitysmuotoihin. Esimerkiksi kääntäjä pdflatex voisi tehdä käännöksen PDF-muotoon, kun taas kielen LarST nimen jakava kääntäjä voisi nimensä mukaisesti olla vastuussa muunnoksesta LaTeX → reStructuredText. LarSTin käyttöönoton helpottamiseksi täytyisi kuitenkin olla olemassa jokin automaattinen tapa siirtää mainittuja reStructuredText-muotoisia oppimateriaaleja LarST-formattiin. Tämän vuoksi tässä diplomityössä toteutettiin kääntäjä nimeltä rSTLa tai ruSTLa, eli reStructuredText to LaTeX. Kääntäjä on kirjoitettu kielellä Rust ja kykenee versiossa 0.38 kääntämään noin 38 erilaista kielen reStructuredText tuntemaa tekstirakennetta LarST-formaattiin. Näihin sisältyvät suuri osa Docutilsin, kuin myös sen laajennosten Sphinx ja A+ rST Tools tarjoamista rakenteista. Kääntäjän lähdekoodi ja dokumentaatio ovat löydettävissä vastaavasti tämän työn lähteistä [1] ja [2]. The formal language reStructuredText is in wide use as a source code of online study materials in computer science and mathematics, written for the learning management system A+, developed at Aalto University. Thus far it has been difficult to tranform the sources into high quality presentation formats, other than HTML pages. A possible solution to this problem is provided by a subset or fragment of the language LaTeX, called LarST or LaTeX to reStructuredText, that is transformable to different presentation formats or intermediary source code via different compilers. For example, a transformation to PDF form is achievable via the compiler pdflatex, whereas the transformation LaTeX → reStructuredText can be performed by a compiler that shares its name with LarST. In order to ease the adoption of LarST, there should exist some automatic means of translating the already mentioned existing libary of study materials into the LarST format. That is why a compiler called rSTLa or ruSTLa, short for reStructuredText to LaTeX, was developed along with this Master’s Thesis. The compiler was written in the Rust programming language and as of version 0.38, it provides support for roughly 38 reStructuredText language constructs, being able to transform them into LarST. These constructs include many of the text elements provided by the standard implementation of reStructuredText, Docutils, but also by its extensions Sphinx and A+ rST Tools. The locations of the source code and documentation of ruSTLa can be found from the reference entries [1] and [2] of this work, respectively.

Актуальность. В этой автобиографической статье В.И. Левин с позиции состоявшегося ученого осмысливает сделанное им в науке, влияние сделанного на науку и общество, пытается спрогнозировать будущее развитие науки с учетом его достижений. Цель статьи – на примере результатов научной работы В.И. Левина сформировать у начинающих ученых понимание фундаментальных процессов эволюционного и революционного подходов к формированию новых научных знаний, закономерностей развития теории и практики благодаря новым фундаментальным открытиям, роли личности ученого в развитии науки. Результат. Для достижения цели статьи использованы личные воспоминания В.И. Левина, его труды, а также воспоминания его коллег и родственников. В статье изложен смысл основных его научных достижений: построение, на основе принципа малого параметра, теории надежности дискретных устройств, открытие математической модели динамики таких устройств в терминах непрерывной логики, разработка методов оптимизации систем в условиях неопределенности в терминах интервальной математики и др. Воссоздана также научная биография В.И. Левина. Новизна и теоретическая значимость. В статье впервые в сжатой форме изложены итоги 60-летнего творческого пути В.И. Левина. Работа будет полезна молодым ученым, изучающим методологию научных исследований, а также специалистам, работающим над сложными научно-техническими проблемами, в качестве примера их успешного разрешения., Relevance. In this autobiographical article, V. I. Levin, from the position of an established scientist, comprehends what he has done in science, the impact of what he has done on science and The purpose of the article society, tries to predict the future development of science taking into account his achievements. is to form an understanding of the fundamental processes of evolutionary and revolutionary approaches to the formation of new scientific knowledge, the laws of the development of theory and practice due to new fundamental discoveries, the role of the scientist's personality in the development of science, using the example of the results of V. I. Levin's scientific work. Result. To achieve the purpose of the article, the personal memories of V. I. Levin, his works, as well as the memories of his colleagues and relatives are used. The article describes the meaning of his main scientific achievements: the construction, based on the principle of a small parameter, of the theory of reliability of discrete devices, the discovery of a mathematical model of the dynamics of such devices in terms of continuous logic, the development of methods for optimizing systems under uncertainty in terms of interval mathematics, etc. The scientific biography of V. I. Levin is also recreated. Novelty and theoretical significance. The article presents for the first time in a concise form the results of the 60-year creative path of V. I. Levin. The work will be useful for young scientists studying the methodology of scientific research, as well as for specialists working on complex scientific and technical problems, as an example of their successful resolution.

We show how to systematically derive an efficient regular expression (regex) matcher using a variety of program transformation techniques, but very little specialized formal language and automata theory. Starting from the standard specification of the set-theoretic semantics of regular expressions, we proceed via a continuation-based backtracking matcher, to a classical, table-driven state machine. All steps of the development are supported by self-contained (and machine-verified) equational correctness proofs.

Theory of computation deals with developing mathematical models of computation. This area of research is divided into three subareas: complexity theory, computability theory and automata theory. We mostly review basic structures of automata theory which are languages and finite state automata in this chapter. A language is defined over a set of symbols called an alphabet. A finite state machine is a mathematical tool to model a computing system. Unlike a combinational circuit, a finite state machine has a memory and its behavior and output depends on its current input and its current state. A finite state automata is a finite state machine with no outputs; instead, it has final states called accepting states. A finite state automata can be used to recognize a language conveniently. We review languages, finite state machines, finite state automata, language recognition in this chapter and conclude the first part with the Turing machine named after Alan Turing, which is a more general type of a finite state machine. We then have a short review of complexity theory with the basic complexity classes.

In the constrained synchronization problem we ask if a given automaton admits a synchronizing word coming from a fixed regular constraint language. We show that intersecting a given constraint language with an ideal language does not increase the computational complexity. Additionally, we state a theorem giving \(\textsf {PSPACE}\)-hardness that broadly generalizes previously used constructions and a result on how to combine languages by concatenation to get polynomial time solvable constrained synchronization problems. We use these results to give a classification of the complexity landscape for small constraint automata of up to three states.

In this paper we introduce the notion of derivation in product (direct product) of additively idempotent semirings. These semirings are useful and important tools in diverse areas such as design of switching circuits, automata theory, information systems, dynamic programming and decision theory. We study hereditary derivations, inner derivations and obtain a representation of an arbitrary derivations which are zero on the multipliers.

We investigate the constrained synchronization problem for weakly acyclic, or partially ordered, input automata. We show that, for input automata of this type, the problem is always in \(\textsf {NP}\). Furthermore, we give a full classification of the realizable complexities for constraint automata with at most two states and over a ternary alphabet. We find that most constrained problems that are PSPACE-complete in general become NP-complete. However, there also exist constrained problems that are PSPACE-complete in the general setting but become polynomial time solvable when considered for weakly acyclic input automata. We also investigate two problems related to subset synchronization, namely if there exists a word mapping all states into a given target subset of states, and if there exists a word mapping one subset into another. Both problems are \(\textsf {PSPACE}\)-complete in general, but in our setting the former is polynomial time solvable and the latter is \(\textsf {NP}\)-complete.

The history of vision can go back around 543 BC. From fossil studies, researchers found out that no. of animal species floats out and soon develops the first animal with eyes. As evolution in bigger species around fifty percent of neurons in our body are involved in the visual processing. Vision allows human to perceive, comprehend, and understand surrounding them while computer vision aims to duplicate the impact of human vision electronically in the form of images. The history of making artificial vison starts around 1545, Gemma Frisius, and Encylopedie in eighteenth century. The foundation period of the concept lies from 1943 to 1956, during this period research is cantered towards understanding the concept of machine learning intelligence, artificial neural system, and automata theory computation. The first work in the field of Artificial intelligence in computer vision and image processing was done in MIT called “Summer Vision Project”. The rise of artificial intelligence starts and it is used widely in every field of technology. As the technology advances machine learning is used in almost every field. This book chapter provides you some details how the machine learning is used in image processing and to solve the current problem and challenge in computer vison like: Denoising, Image compression, Image color enhancement, segmentation, etc. Machine learning algorithm like Neural Network, Support Vector Machine, Genetic Algorithm, Convolutional Neural Network, etc. were discussed in the book chapter.