Search results for "Formal languages"
showing 10 items of 322 documents
FO^2 with one transitive relation is decidable
2013
We show that the satisfiability problem for the two-variable first-order logic, FO^2, over transitive structures when only one relation is required to be transitive, is decidable. The result is optimal, as FO^2 over structures with two transitive relations, or with one transitive and one equivalence relation, are known to be undecidable, so in fact, our result completes the classification of FO^2-logics over transitive structures with respect to decidability. We show that the satisfiability problem is in 2-NExpTime. Decidability of the finite satisfiability problem remains open.
Alignment-free sequence comparison using absent words
2018
Sequence comparison is a prerequisite to virtually all comparative genomic analyses. It is often realised by sequence alignment techniques, which are computationally expensive. This has led to increased research into alignment-free techniques, which are based on measures referring to the composition of sequences in terms of their constituent patterns. These measures, such as $q$-gram distance, are usually computed in time linear with respect to the length of the sequences. In this paper, we focus on the complementary idea: how two sequences can be efficiently compared based on information that does not occur in the sequences. A word is an {\em absent word} of some sequence if it does not oc…
Sense Equivalence in plWordNet to Princeton WordNet Mapping
2019
Abstract Though the interest in use of wordnets for lexicography is (gradually) growing, no research has been conducted so far on equivalence between lexical units (or senses) in inter-linked wordnets. In this paper, we present and validate a procedure of sense-linking between plWordNet and Princeton WordNet. The proposed procedure employs a continuum of three equivalence types: strong, regular and weak, distinguished by a custom-designed set of formal, semantic and translational features. To validate the procedure, three independent samples of 120 sense pairs were manually analysed with respect to the features. The results show that synsets from the two wordnets linked by interlingual syno…
Who is looking at me? The cone of gaze widens in social phobia
2011
Gaze direction is an important cue that regulates social interactions and facilitates joint attention. Although humans are very accurate in determining gaze directions in general, they have a surprisingly liberal criterion for the presence of mutual gaze. Using an established psychophysical task that required observers to adjust the eyes of a virtual head to the margins of the area of mutual gaze, we examined whether the resulting cone of gaze is altered in people with social phobia. It turned out that during presence of a second virtual person, the gaze cone's width was specifically enlarged in patients with social phobia as compared to healthy controls. The size of this effect was correla…
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…