Search results for " Languages"
showing 10 items of 1859 documents
TWO-DIMENSIONAL FINITE STATE RECOGNIZABILITY
1996
The purpose of this paper is to investigate about a new notion of finite state recognizability for two-dimensional (picture) languages. This notion takes as starting point the characterization of one-dimensional recognizable languages in terms of local languages and projections. Such notion can be extended in a natural way to the two-dimensional case. We first introduce a notion of local picture language and then we define,a recognizable picture language as a projection of a local picture language. The family of recognizable picture languages is denoted by REC. We study some combinatorial and language-theoretic properties of family REC. In particular we prove some closure properties with re…
Inductive synthesis of dot expressions
2005
We consider the problem of the synthesis of algorithms by sample computations. We introduce a formal language, namely, the so-called dot expressions, which is based on a formalization of the intuitive notion of ellipsis (‘...’). Whilst formally the dot expressions are simply a language describing sets of words, on the other hand, it can be considered as a programming language supporting quite a wide class of programs. Equivalence and asymptotical equivalence of dot expressions are defined and proved to be decidable. A formal example of a dot expression is defined in the way that, actually, it represents a sample computation of the program presented by the given dot expression. A system of s…
Multi-letter reversible and quantum finite automata
2007
The regular language (a+b)*a (the words in alphabet {a, b} having a as the last letter) is at the moment a classical example of a language not recognizable by a one-way quantum finite automaton (QFA). Up to now, there have been introduced many different models of QFAs, with increasing capabilities, but none of them can cope with this language. We introduce a new, quite simple modification of the QFA model (actually even a deterministic reversible FA model) which is able to recognize this language. We also completely characterise the set of languages recognizable by the new model FAs, by finding a "forbidden construction" whose presence or absence in the minimal deterministic (not necessaril…
Automatic calculation of massive two-loop self-energies with XLOOPS
1997
Abstract Within the program package XLOOPS it is possible to calculate self-energies up to the two-loop level for arbitrary massive particles. The program package — written in MAPLE (Char et al., Maple V Language Reference Manual (Springer, 1991); Char et al., Maple V Library Reference Manual (Springer, 1991)) — is designed to deal with the full tensor structure of the occurring integrals. This means that applications are not restricted to those cases where the reduction to scalars via equivalence theorem is allowed. The algorithms handle two-loop integrals analytically if this is possible. For those topologies where no analytic result for the general mass case is available, the diagrams ar…
GEOMETRIC EQUIVALENCE OF ALGEBRAS
2001
In this paper, we study the geometric equivalence of algebras in several varieties of algebras. We solve some of the problems formulated in [2], in particular, that of geometric equivalence for real-closed fields and finitely generated commutative groups.
Algebraic Results on Quantum Automata
2004
We use tools from the algebraic theory of automata to investigate the class of languages recognized by two models of Quantum Finite Automata (QFA): Brodsky and Pippenger’s end-decisive model, and a new QFA model whose definition is motivated by implementations of quantum computers using nucleo-magnetic resonance (NMR). In particular, we are interested in the new model since nucleo-magnetic resonance was used to construct the most powerful physical quantum machine to date. We give a complete characterization of the languages recognized by the new model and by Boolean combinations of the Brodsky-Pippenger model. Our results show a striking similarity in the class of languages recognized by th…
Sequential formula translation
1983
The syntax of an algorithmic language such as ALGOL is conveniently described as a sequence of states indicated by an element called cellar. Transitions are controlled by admissible state- s ymbol pairs which may be represented by a transition matrix. This description of syntax furnishes at the same time an extremely simple rule for translating into machine programs statements in the algorithmic language. Sequential treatment, however, is not feasible in the case of certain optimizing processes such as recursive address calculation.
On Combinatorial Generation of Prefix Normal Words
2014
A prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. This class of words is important in the context of binary jumbled pattern matching. In this paper we present an efficient algorithm for exhaustively listing the prefix normal words with a fixed length. The algorithm is based on the fact that the language of prefix normal words is a bubble language, a class of binary languages with the property that, for any word w in the language, exchanging the first occurrence of 01 by 10 in w results in another word in the language. We prove that each prefix normal word is produced in O(n) amortized time, and conjecture, based on expe…
Linguistic Analysis and Ancient Indo-European Languages
2015
Using modern linguistic theory to describe ‘dead’ languages is one of the theoretical and methodological challenges in contemporary linguistic research. In fact, theories of the twentieth century mostly aimed to account for speakers’ linguistic competence, thus basing their analysis on live speakers and their intuitions. However, drawing on evidence from languages such as Vedic, Greek, Latin, Hittite, Gothic, Celtic and Proto-Indo-European itself, the relevance of the ancient Indo-European languages to contemporary linguistic theory has been constantly shown, since the rise of the linguistic sciences in the early nineteenth century. In fact, the observation of ancient Indo-European language…
Aktuālas valodu un literatūras mācību problēmas
1994
Rakstu krājumā iztirzātas vairākas pedagoģiskām augstskolām un vispārizglītojošām skolām aktuālas valodu un latviešu literatūras mācību problēmas.