Search results for "Formal language"
showing 10 items of 357 documents
A trie-based approach for compacting automata
2004
International audience; We describe a new technique for reducing the number of nodes and symbols in automata based on tries. The technique stems from some results on anti-dictionaries for data compression and does not need to retain the input string, differently from other methods based on compact automata. The net effect is that of obtaining a lighter automaton than the directed acyclic word graph (DAWG) of Blumer et al., as it uses less nodes, still with arcs labeled by single characters.
Pattern languages with and without erasing
1994
The paper deals with the problems related to finding a pattern common to all words in a given set. We restrict our attention to patterns expressible by the use of variables ranging over words. Two essentially different cases result, depending on whether or not the empty word belongs to the range. We investigate equivalence and inclusion problems, patterns descriptive for a set, as well as some complexity issues. The inclusion problem between two pattern languages turns out to be of fundamental theoretical importance because many problems in the classical combinatorics of words can be reduced to it.
Using Attribute Grammars for Description of Inductive Inference Search Space
1998
The problem of practically feasible inductive inference of functions or other objects that can be described by means of an attribute grammar is studied in this paper. In our approach based on attribute grammars various kinds of knowledge about the object to be found can be encoded, ranging from usual input/output examples to assumptions about unknown object's syntactic structure to some dynamic object's properties. We present theoretical results as well as describe the architecture of a practical inductive synthesis system based on theoretical findings.
The Expressibility of Languages and Relations by Word Equations
1997
Classically, several properties and relations of words, such as being a power of a same word, can be expressed by using word equations. This paper is devoted to study in general the expressive power of word equations. As main results we prove theorems which allow us to show that certain properties of words are not expressible as components of solutions of word equations. In particular, the primitiveness and the equal length are such properties, as well as being any word over a proper subalphabet.
Adaptation of a German Multidimensional Networking Scale into English
2011
Networking refers to building and maintaining personal contacts in order to obtain resources that, in turn, enhance one’s career success and work performance. This study reports the translation and adaptation of a multifaceted German networking scale ( Wolff & Moser, 2006 ) into English and focuses on the equivalence of the two language versions. Going beyond the often used translation-backtranslation method, we used a parallel translation-backtranslation method in combination with two expert committees to arrive at the English scale version, aiming to obtain at least structural equivalence. We utilize a bilingual sample (N = 76) as well as monolingual samples from the US (N = 174) and…
A word prediction methodology for automatic sentence completion
2015
Word prediction generally relies on n-grams occurrence statistics, which may have huge data storage requirements and does not take into account the general meaning of the text. We propose an alternative methodology, based on Latent Semantic Analysis, to address these issues. An asymmetric Word-Word frequency matrix is employed to achieve higher scalability with large training datasets than the classic Word-Document approach. We propose a function for scoring candidate terms for the missing word in a sentence. We show how this function approximates the probability of occurrence of a given candidate word. Experimental results show that the proposed approach outperforms non neural network lang…
BALANCE PROPERTIES AND DISTRIBUTION OF SQUARES IN CIRCULAR WORDS
2010
We study balance properties of circular words over alphabets of size greater than two. We give some new characterizations of balanced words connected to the Kawasaki-Ising model and to the notion of derivative of a word. Moreover we consider two different generalizations of the notion of balance, and we find some relations between them. Some of our results can be generalized to non periodic infinite words as well.
Turing's Error-revised
2016
Many important lines of argumentation have been presented during the last decades claiming that machines cannot think like people. Yet, it has been possible to construct devices and information systems, which replace people in tasks which have previously been occupied by people as the tasks require intelligence. The long and versatile discourse over, what machine intelligence is, suggests that there is something unclear in the foundations of the discourse itself. Therefore, we critically studied the foundations of used theory languages. By looking critically some of the main arguments of machine thinking, one can find unifying factors. Most of them are based on the fact that computers canno…
Varieties Generated by Certain Models of Reversible Finite Automata
2006
Reversible finite automata with halting states (RFA) were first considered by Ambainis and Freivalds to facilitate the research of Kondacs-Watrous quantum finite automata. In this paper we consider some of the algebraic properties of RFA, namely the varieties these automata generate. Consequently, we obtain a characterization of the boolean closure of the classes of languages recognized by these models.
Theory languages in designing artificial intelligence
2023
The foundations of AI design discourse are worth analyzing. Here, attention is paid to the nature of theory languages used in designing new AI technologies because the limits of these languages can clarify some fundamental questions in the development of AI. We discuss three types of theory language used in designing AI products: formal, computational, and natural. Formal languages, such as mathematics, logic, and programming languages, have fixed meanings and no actual-world semantics. They are context- and practically content-free. Computational languages use terms referring to the actual world, i.e., to entities, events, and thoughts. Thus, computational languages have actual-world refer…