Search

In this paper a platform is presented, that given a stochastic context-free grammar (SCFG), automatically outputs the description of the parser in synthesizable hardware description language (HDL) which can be downloaded in an Field Programmable Gate Arrays (FPGA) board. Initially, according to our methodology the SCFG is augmented with attributes which store the probability values and can be evaluated through corresponding stack actions. The architecture of the produced system is based on a proposed extension of Earley's parallel algorithm, which given an input string, generates the parse trees in the form of an AND-Or parse tree. This AND-or parse tree is then traversed using a proposed tree traversal technique in order to execute the corresponding actions in the correct order, so as to compute the necessary probabilities. The platform is suitable for embedded systems applications where a natural language interface is required or in pattern recognition tasks. The parser generated by the presented platform has been tested for various SCFGs and compared to software approaches. The performance comparison is one to two orders of magnitude in favor of the presented hardware, compared to previous software approaches, depending on the application, the input string length and the number of produced trees. [ABSTRACT FROM AUTHOR]

In this paper, the descriptional complexity of extended finite splicing systems is studied. These systems are known to generate exactly the class of regular languages. Upper and lower bounds are shown relating the size of these splicing systems, defined as the total length of the rules and the initial language of the system, to the size of their equivalent minimal nondeterministic finite automata (NFA). In addition, an accepting model of extended finite splicing systems is studied. Using this variant one can obtain systems which are more than polynomially more succinct than the equivalent NFA or generating extended finite splicing system. [ABSTRACT FROM AUTHOR]

In this paper finite state recognizers are considered as unary tree recognizers with unary operational symbols. We introduce translation recognizers of a tree recognizer, which are finite state recognizers whose operations are the elementary translations of the underlying algebra of the considered tree recognizer. In terms of translation recognizers we give general conditions under which a class of recognizable tree languages with a given property can be determined by a class of monoids determining the class of string languages having the same property. [ABSTRACT FROM AUTHOR]

Extended finite automata are finite state automata equipped with the additional ability to apply an operation on the currently remaining input word, depending on the current state. Hybrid extended finite automata can choose from a finite set of such operations. In this paper, five word operations are taken into consideration which always yield letter-equivalent results, namely reversal and shift operations. The computational power of those machines is investigated, locating the corresponding families of languages in the Chomsky hierarchy. Furthermore, different types of hybrid extended finite automata, defined by the set of operations they are allowed to apply, are compared with each other, demonstrating that there exist dependencies and independencies between the input manipulating operations. [ABSTRACT FROM AUTHOR]

In this paper, we present a process algebra aimed at modelling PKI-based systems. The new language, SPIKY, extends the spi-calculus by adding primitives for the retrieval of certified/uncertified public keys as well as private keys belonging to users of the PKI-based system. SPIKY also formalises the notion of process ownership by PKI users, which is necessary in controlling the semantics of the key retrieval capabilities. We also construct a static analysis for SPIKY that captures the property of term substitutions resulting from message-passing and PKI/cryptographic operations. This analysis is shown to be safe and computable. Finally, we use the analysis to define the term secrecy and peer participation properties for a couple of examples of authentication protocols. [ABSTRACT FROM AUTHOR]

In this paper, we describe in detail a novel SQL service based on radix tree data structures and we show how to multithread the service in order to execute it on distributed platforms. The SQL service is currently developed in the context of SMP platforms but should be deployed in the future on grid platforms. The development of the SQL service is part of the Grid Explorer project. The project (French part) aims at building a grid emulator to study the behavior of grids. One need in the project is for a database software to store experimental conditions and to analyze traces of execution (for instance, to find in "real time" frequent episodes for the CPU load metric in order to predict the future state of the grid). We plan to use our SQL service on an SMP platform for this purpose. [ABSTRACT FROM AUTHOR]

The paper investigates two-dimensional recognizable languages that are defined by the so-called "dot systems" that are special subgroups of (ℤ/2ℤ)ℤ2. The dot shapes that provide directional transitivity or mixing for the related language are investigated. It is shown that languages defined by parallelogram shapes fail to be transitive in the direction of a defining vector and hence fail to be mixing, while certain triangular shapes guarantee that the factor language of the associated dot system will be mixing. Dot systems belong to a class of two-dimensional shift spaces that have a factor language such that every admissable block can be extended to a configuration of the entire plane. For this class of shift spaces we introduce a finite graph (i.e., a finite state automaton) that recognizes two-dimensional local languages, then show that certain transitivity properties may be observed from the structure of the finite graph. [ABSTRACT FROM AUTHOR]

One of the new approaches to data classification uses prefix codes and finite state automata as representations of prefix codes. A prefix code is a (possibly infinite) set of strings such that no string is a prefix of another one. An important task driven by the need for the efficient storage of such automata in memory is the decomposition (in the sense of formal languages concatenation) of prefix codes into prime factors. We investigate properties of such prefix code decompositions. A prime decomposition is a decomposition of a prefix code into a concatenation of nontrivial prime prefix codes. A prefix code is prime if it cannot be decomposed into at least two nontrivial prefix codes. In the paper a linear time algorithm is designed which finds the prime decomposition F[sub 1]F[sub 2]…F[sub k] of a regular prefix code F given by its minimal deterministic automaton. Our results are especially interesting for infinite regular prefix codes. [ABSTRACT FROM AUTHOR]

Regular expressions are used in many practical applications. Practical regular expressions are commonly called "regex". It is known that regex are different from regular expressions. In this paper, we give regex a formal treatment. We make a distinction between regex and extended regex; while regex represent regular languages, extended regex represent a family of languages larger than regular languages. We prove a pumping lemma for the languages expressed by extended regex. We show that the languages represented by extended regex are incomparable with context-free languages and a proper subset of context-sensitive languages. Other properties of the languages represented by extended regex are also studied. [ABSTRACT FROM AUTHOR]

A deterministic finite automaton (DFA) [formula] is called a cover automaton (DFCA) for a finite language L over some alphabet Σ if [formula], with l being the length of some longest word in L. Thus a word w ∈ Σ* is in L if and only if |w| ≤ l and [formula]. The DFCA [formula] is minimal if no DFCA for L has fewer states. In this paper, we present an algorithm which converts an n–state DFA for some finite language L into a corresponding minimal DFCA, using only O(n log n) time and O(n) space. The best previously known algorithm requires O(n[sup 2]) time and space. Furthermore, the new algorithm can also be used to minimize any DFCA, where the best previous method takes O(n[sup 4]) time and space. Since the required data structure is rather complex, an implementation in the common programming language C/C++ is also provided. [ABSTRACT FROM AUTHOR]

We present a generic aproach to the static analysis of concurrent programs with procedures. We model programs as communicating pushdown systems. It is known that typical dataflow problems for this model are undecidable, because the emptiness problem for the intersection of context-free languages, which is undecidable, can be reduced to them. In this paper we propose an algebraic framework for defining abstractions (upper approximations) of context-free languages. We consider two classes of abstractions: finite-chain abstractions, which are abstractions whose domains do not contain any infinite chains, and commutative abstractions corresponding to classes of languages that contain a word if and only if they contain all its permutations. We show how to compute such approximations by combining automata theoretic techniques with algorithms for solving systems of polynomial inequations in Kleene algebras. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the notion of distributed ω-automata. Distributed ω-automata are a group of automata working in unison to accept an ω-language. We build the theory of distributed ω-automata for finite state automata and pushdown automata in different modes of cooperation like the t-mode, *-mode, = k-mode, ≤ k-mode and ≥ k-mode along with different acceptance criteria i.e. Büchi-, Muller-, Rabin- and Streett- acceptance criteria. We then analyze the acceptance power of such automata in all the above modes of cooperation and acceptance criteria. We present proofs that distributed ω-finite state automata do not have any additional power over ω-finite state automata in any of the modes of cooperation or acceptance criteria, while distributed ω-pushdown automata can accept languages not in CFL[sub ω]. We give proofs for the equivalence of all modes of cooperation and acceptance criteria in the case of distributed ω-pushdown automata. We show that the power of distributed ω-pushdown automata is equal to that of ω-Turing Machines. We also study the deterministic version of distributed ω-pushdown automata. Deterministic ω-pushdown automata accept only languages contained in CFL[sub ω] but distributed deterministic ω-pushdown automata can accept languages not in CFL[sub ω] and have the same power as their nondeterministic counterparts. We also define distributed completely deterministic ω-pushdown automata and analyze their power. [ABSTRACT FROM AUTHOR]