Search

A new approach in detecting and identifying power quality disturbances is presented. The use of Formal Language Theory, already exploited in other fields, was used to develop an innovative tool to identify patterns in electrical signals. The Concordia transform is applied to the 3-phase electrical system, composing a 2-D signal. The obtained signal is computed with a ˵healthy″ 3-phase composed signal, retrieving new data. A Formal Language based inference algorithm is used to infer a grammar from this new data. Each type of fault has its own grammar, which allows the developed algorithm to easily detect and identify the disturbances. [ABSTRACT FROM AUTHOR]

We study one-head machines through symbolic and topological dynamics. In particular, a subshift is associated to the subshift, and we are interested in its complexity in terms of realtime recognition. We emphasize the class of one-head machines whose subshift can be recognized by a deterministic pushdown automaton. We prove that this class corresponds to particular restrictions on the head movement, and to equicontinuity in associated dynamical systems. [ABSTRACT FROM AUTHOR]

We give a new proof for the fact that measure-many one-way quantum finite automata (MM-1QFA) recognize only regular languages with bounded error. Our proof, different from the one in the literature, gives another insight to the recognition power of MM-1QFA. Moreover, we generalize the proof to a broader class of automata that include probabilistic automata and some kinds of quantum finite automata. In addition, we briefly discuss the equivalence problem of some quantum computing models in a uniform framework. [ABSTRACT FROM AUTHOR]

In this paper the concepts of the graph of generative grammars and Lindenmayer systems are investigated. These special and-or graphs represent all information about the grammar. For regular grammars the new concept is equivalent to the finite automata. In context-free case it is an extension of the dependency graph. We also analyze how it is related to programmed grammars (using context-free rules). Moreover the graph of the grammar is more general; it can be defined for generative grammars to any recursive enumerable languages containing all information of the grammar. By the help of tokens the new concept can effectively be used to follow derivations. Moreover parallel derivations can be simulated in non-linear grammars. While in regular and linear case only sequential derivations are going, in context-free case a kind of maximal parallelism can be involved. In context-sensitive case communication/synchronization is also needed in these processes. The Lindenmayer systems are well-known parallel rewriting systems; our concept also can be defined and used for various Lindenmayer systems. Especially the main difference is not in the graph form, but in the simulation process. [ABSTRACT FROM AUTHOR]

The hairpin completion is a natural operation of formal languages which has been inspired by molecular phenomena in biology and by DNA-computing. We consider here a new variant of the hairpin completion, called hairpin lengthening, which seems more appropriate for practical implementation. The variant considered here concerns the lengthening of the word that forms a hairpin structure, such that this structure is preserved, without necessarily completing the hairpin. Although our motivation is based on biological phenomena, the present paper is more about some algorithmic properties of this operation. We prove that the iterated hairpin lengthening of a language recognizable in ]> time is recognizable in ]> time, while the one-step hairpin lengthening of such a language is recognizable in ]> time. Finally, we propose an algorithm for computing the hairpin lengthening distance between two words in quadratic time. [ABSTRACT FROM AUTHOR]

This paper introduces an algebraic theory SystemC픽핃 tlm that can be used to specify and analyse the behaviour of SystemC designs. This theory/language is the successor of the SystemC픽핃 language. It extends SystemC픽핃 with the possibility to define process term instantiations and the use of SystemC positional connections/named connection and Transaction Level Modelling (TLM). We illustrate the practical use of SystemC픽핃tim by means of a TLM example. [ABSTRACT FROM AUTHOR]

A word w over an alphabet Σ is n-synchronizing if it resets every (n + 1)-state synchronizing automaton over this alphabet. For a fixed n and Σ, n-synchronizing words can be recognized in polynomial time, yet no practical algorithm is known. In this paper we show that one cannot expect to find such an algorithm. We prove that the problem of recognizing 2-synchronizing words, where the input consists of a word and an alphabet, is co-NP-complete. We also show that the length of a 2-synchronizing word is at least 2|Σ|2, which improves the lower bound known so far. [ABSTRACT FROM AUTHOR]

This is a tutorial based on a course delivered as part of the International PhD School in Formal Languages and Applications located at the Rovira i Virgili University in Tarragona, Spain. It is focused on an application of formal language theory to represent behaviours of concurrent systems necessitating a generalisation of language theory to traces, which originates with the work of Mazurkiewicz in 1977. The tutorial uses Petri nets as an underlying system model which allows one to clearly distinguish between causality and independence between executions of actions, a major feature of concurrent behaviour. [ABSTRACT FROM AUTHOR]

The concept of a Parikh matrix or an extended Parikh mapping of words introduced by Mateescu et al (2001) is formulated here for two-dimensional (2D) arrays. A polynomial time algorithm is proposed to reconstruct an unknown 2D-array over { 0,1 } from its image under the extended Parikh mapping along a single direction. On the other hand the problem of reconstructing a 2D-array over { 0,1 } from its image under the extended Parikh mapping along three or more directions is shown to be NP-hard. Also a polynomial time algorithm to reconstruct a 2D-array over {0,1} with a maximum number of ones close to the main diagonal of the array is presented by reducing the problem to Min-cost Max-flow problem. [ABSTRACT FROM AUTHOR]

ACPhssrt is a hybrid process algebra obtained by extending a combination of two existing extensions of Algebra of Communicating Processes (ACP), namely the process algebra with continuous relative timing and the process algebra with propositional signals, for the specification and analysis of hybrid systems. In addition to equational axioms, this hybrid process algebra has rules to derive equations with the help of real analysis. ACPhssrt is also closely related to the theory of hybrid automata, so ACPhssrt can be reasonable easily translated to hybrid automata. This enables automatic verification of ACPhssrt specifications using existing hybrid automaton-based verification tools (e.g. PHAVer and HyTech). Since ACPhssrt is a well-developed algebraic theory from the field of hybrid process algebras with the above-mentioned features, it seems to allow rigorous specification and analysis of digital/analog/mixed-signal circuits. In order to explore this fact, in this paper, we study a mixed-signal circuit: a half wave rectifier in ACPhssrt. Some basic properties of the half wave rectifier are analysed in a formal way and some correctness requirements are also proven to be satisfied. [ABSTRACT FROM AUTHOR]

Part two of the book "Introducing Postmodernism" is presented. It explores the origins of postmodern theory and its roots that can be traced to the school of formal linguistics, structuralism, which was founded by Swiss linguistics professor Ferdinand de Saussure. It highlights the problems encountered in linguistics and the view of Saussure's that a set of linguistic meanings can be formed through a set of sounds called phonemes that can create different meanings. Defects in structuralism such as dematerialization and formalism are mentioned.

A definition of the term "Backus-Naur form (BNF)" is presented. Also known as the Backus-Naur formalism, Backus normal form, or Panini-Backus form, BNF refers to a metasyntax used to express context-free grammars. It is widely used as a notation for the grammars of computer programming languages, command sets and communication protocols, as well as a notation for representing parts of natural language grammars.

An encyclopedia entry for the term "Augmented Backus--Naur Form" (ABNF) is presented. It refers to a metasyntax used to express context-free grammars, which describes formal languages consisting of its own syntax and derivation rules. Such metalanguage explains a formal system of language pertaining to a protocol. This description of the ABNF is included in RFC 4234 and often serves as the definition language for IETF communication protocol.