共查询到20条相似文献,搜索用时 15 毫秒
1.
Gerald S. Eisman 《Theoretical computer science》1984,29(3):325-349
EDTOL systems can be used to approximate real numbers by considering the limit of the ratio of the number of occurences of one symbol to the number of occurences of another symbol in a sequence of derived words of increasing length. The complexity of this limit value is shown to be related to the structure of the generating system. 相似文献
2.
Pedro García Manuel Vázquez de Parga Antonio Cano Damián López 《Theoretical computer science》2009,410(47-49):4961-4974
There exist several works that study the class of reversible languages defined as the union closure of 0-reversible languages, their properties and suitable representations. In this work we define and study the class of locally reversible languages, defined as the union closure of -reversible languages. We characterize the class and prove that it is a local (positive) variety of formal languages. We also extend the definition of quasi-reversible automata to deal with locally reversible languages and propose a polynomial algorithm to obtain, for any given locally -reversible language, a quasi--reversible automaton. 相似文献
3.
4.
In this paper we revisit the semantics of extended regular expressions (regex), defined succinctly in the 90s [A.V. Aho, Algorithms for finding patterns in strings, in: Jan van Leeuwen (Ed.), Handbook of Theoretical Computer Science, in: Algorithms and Complexity, vol. A, Elsevier and MIT Press, 1990, pp. 255–300] and rigorously in 2003 by Câmpeanu, Salomaa and Yu [C. Câmpeanu, K. Salomaa, S. Yu, A formal study of practical regular expressions, IJFCS 14 (6) (2003) 1007–1018], when the authors reported an open problem, namely whether regex languages are closed under the intersection with regular languages. We give a positive answer; and for doing so, we propose a new class of machines — regex automata systems (RAS) — which are equivalent to regex. Among others, these machines provide a consistent and convenient method of implementing regex in practice. We also prove, as a consequence of this closure property, that several languages, such as the mirror language, the language of palindromes, and the language of balanced words are not regex languages. 相似文献
5.
6.
The Object Constraint Language (OCL) is a well-accepted ingredient in model-driven engineering and accompanying modeling languages such as UML (Unified Modeling Language) and EMF (Eclipse Modeling Framework) that support object-oriented software development. Among various possibilities, OCL offers the formulation of class invariants and operation contracts in form of pre- and postconditions, and side-effect free query operations. Much research has been done on OCL and various mature implementations are available for it. OCL is also used as the foundation for several modeling-specific programming and transformation languages. However, an intrusive way of embedding OCL into these language hampers us when we want to benefit from the existing achievements for OCL. In response to this shortcoming, we propose the language SOIL (Simple OCL-like Imperative Language), which we implemented in the UML and OCL modeling tool USE to amend its declarative model validation features. The expression sub-language of SOIL is identical to OCL. SOIL adds imperative constructs for programming in the domain of models. Thus by employing OCL and SOIL, it is possible to describe any operation in a declarative way and in an operational way on the modeling level without going into the details of a conventional programming language. In contrast to other similar approaches, the embedding of OCL into SOIL is done in a careful, non-intrusive way so that purity of OCL is preserved. 相似文献
7.
Paavo Turakainen 《Information Sciences》1981,24(3):229-253
Using a simple method we find some nonstochastic and stochastic languages related to the Dyck sets and to the languages and . Using the theory of uniformly distributed sequences, we present a sufficient condition for a one-letter language to be nonstochastic. Among the applications is the result that {ap¦p is a prime} is nonstochastic. We also study the images of stochastic and rational stochastic languages under nonerasing and arbitrary homomorphisms as well as their relations to some well-known families. Finally, we introduce a large class of bounded languages and show that it is contained in /of∩ (DUP) = the smallest intersection-closed AFL containing , which is a subfamily of /oK(/oLQ = the image of the family of rational stochastic languages under nonerasing homomorphisms. 相似文献
8.
Stéphane Grumbach Zoé Lacroix 《Annals of Mathematics and Artificial Intelligence》1997,19(1-2):169-213
Non-deterministic computation is not really computation, but the difference with real computation is blurred. We study in detail various levels of non-determinism in computations on non-deterministic Turing machines with polynomial bounds on the resources. Meanwhile, we consider numerous query languages, implicit logic, choice logic, order invariant logic, and restrictions of second-order logic, and establish correspondences between all these formalisms for both deterministic and non-deterministic queries. To the degrees of non-determinism in the computations, correspond levels of non-determinism in the logical definitions. Our main contribution is to characterize various complexity classes between PTIME and PSPACE, by several logical means, thus translating open questions in complexity theory to open questions in logic related to the use of the non-determinism. 相似文献
9.
It is well known that allowing nondeterminism in a finite automaton can produce in the most extreme case an exponential savings in the number of states required to recognize a regular language. This paper studies situations intermediate between forbidding nondeterminism and allowing it. The amount of nondeterminism used by a finite automaton is quantified, so that the decrease in the size of the state space that occurs as the amount of nondeterminism that is permitted increases in increments can be studied. These intermediate situations are shown always to lie between two extremes:(1) there are no savings as the amount of nondeterminism increases incrementally, so that savings occur only when the amount of nondeterminism becomes unlimited;(2) each increment of nondeterminism results in additional savings, the number s of states decreasing approximately as s1/i, until exponential savings have been achieved after about i = logs/log log s increments. 相似文献
10.
11.
Elie Sanchez 《Information Sciences》1978,15(1):45-76
The theory of possibility, recently introduced by L. A. Zadeh, is explored in the particular subject of possibility-qualified propositions as a basis for approximate reasoning. The concept of ε-possibility related to fuzzy sets has a formulation that verifies some criteria of minimal uncertainty. It is shown how to derive possibility-qualified propositions from the classical translation rules in fuzzy logic. 相似文献
12.
Christoph Globig Klaus P. Jantke Steffen Lange Yasubumi Sakakibara 《New Generation Computing》1997,15(1):59-83
Case-based reasoning is deemed an important technology to alleviate the bottleneck of knowledge acquisition in Artificial Intelligence (AI). In case-based reasoning, knowledge is represented in the form of particular cases with an appropriate similarity measure rather than any form of rules. The case-based reasoning paradigm adopts the view that an Al system is dynamically changing during its life-cycle which immediately leads to learning considerations. Within the present paper, we investigate the problem of case-based learning of indexable classes of formal languages. Prior to learning considerations, we study the problem of case-based representability and show that every indexable class is case-based representable with respect to a fixed similarity measure. Next, we investigate several models of case-based learning and systematically analyze their strengths as well as their limitations. Finally, the general approach to case-based learnability of indexable classes of formal languages is prototypically applied to so-called containmet decision lists, since they seem particularly tailored to case-based knowledge processing. 相似文献
13.
14.
15.
16.
Helmut Horacek 《Machine Translation》1996,11(1-3):109-158
Recently, the scientific interest in addressing metonymy phenomena from a computational perspective has increased significantly. Considerable effort is invested in this, but issues addressing metonymy in the context of natural language generation have been widely ignored so far, and also comparable multilingual analyses are rather sparse. Motivated by these shortcomings, we investigate methods for representing knowledge required to express metonymic relations in several ways and in multiple languages, and we present techniques for generating these alternative verbalizations. In particular, we demonstrate how mapping schemata that enable lexical expressions on the basis of conceptual specifications to be built are derived from the Qualia Structure of Pustejovsky's Generative Lexicon. Moreover, our enterprise has led to the exposition of interesting cross-language differences, notably the use of prefixed verbs and compound nouns in German, as opposed to widely equivalent expressions entailing implicit metonymic relations, as frequently found in English. A main achievement of our approach lies in bringing computational lexical semantics and natural language generation closer together, so that the linguistic foundations of lexical choice in natural language generation are strengthened. 相似文献
17.
18.
A class of formal languages (ACML) acceptable by automaton counter machines is considered. This class is shown to be close
with respect to the operations of union, regular intersection, concatenation, infinite iteration, homomorphism, and inverse
homomorphism. It follows from here that this class is a full abstract family of languages [7] with all the properties following
from this. Furthermore, the ACML is close with respect to intersection and substitution but is not closed with respect to
complement and reverse. For the ACML class, the problems of emptiness and recognition of words of a language given by an automaton
counter machine are decidable, but the problems of inclusion and equivalence of languages are undecidable. A comparison with
other classes of languages (regular, context-free, context-sensitive, and Petri-net languages) is performed. 相似文献
19.
Gennaro Costagliola Vincenzo Deufemia Filomena Ferrucci Carmine Gravino 《Information and Computation》2003,187(2):209-245
Drawn symbolic pictures are an extension of drawn pictures obtained by associating a symbol from an alphabet to each point of the picture. In the paper we will address some new interesting issues derived from the introduction of the symbols and we will identify the conditions, which ensure the preservation of properties holding for drawn pictures in the setting of the proposed extension. 相似文献
20.
Summary Geffert has shown that earch recursively enumerable languageL over can be expressed in the formL{h(x)
–1
g(x)x in
+}
* where is an alphabet andg, h is a pair of morphisms. Our purpose is to give a simple proof for Geffert's result and then sharpen it into the form where both of the morphisms are nonerasing. In our method we modify constructions used in a representation of recursively enumerable languages in terms of equality sets and in a characterization of simple transducers in terms of morphisms. As direct consequences, we get the undecidability of the Post correspondence problem and various representations ofL. For instance,L =(L
0)
* whereL
0 is a minimal linear language and is the Dyck reductiona, A. 相似文献