Search results for "Formal languages"
showing 10 items of 322 documents
Negative results in the theory of games with lexicographic utilities
2003
When players may have lexicographic utilities, there are: (i) extensive games having a non-empty set of equilibria but empty sets of sequentially rational, sequential and perfect equilibria (ii) normal form games having a non-empty set of equilibria but an empty set of proper equilibria and no stable set of equilibria and (iii) two extensive games having the same normal form representation and disjoint sets of sequential equilibria.
Some decisional problems on rational relations
1997
Abstract In this paper we prove that the problem of deciding whether a deterministic rational relation is star-free is recursively solvable, although the same problem for any rational relation is undecidable. We also prove that a rational relation is star-free if and only if it is aperiodic and deterministic.
Reduction of UML Class Diagrams
2002
One and the same “real world” can be modeled by different UML class diagrams, which in such a case can be considered “intuitively equivalent”. A formalization of this “intuitive equivalence” of class diagrams is proposed. An algorithm is constructed that for two class diagrams determines if they model the same “real world”. This algorithm can be used in CASE tools to compare alternative models of a system, and for diagram “compression” to facilitate understanding of large diagrams.
The Average State Complexity of the Star of a Finite Set of Words Is Linear
2008
We prove that, for the uniform distribution over all sets Xof m(that is a fixed integer) non-empty words whose sum of lengths is n, $\mathcal{D}_X$, one of the usual deterministic automata recognizing X*, has on average $\mathcal{O}(n)$ states and that the average state complexity of X*is i¾?(n). We also show that the average time complexity of the computation of the automaton $\mathcal{D}_X$ is $\mathcal{O}(n\log n)$, when the alphabet is of size at least three.
Semantic aware RSS query algebra
2010
International audience; Existing XML query algebras are not fully appropriate to retrieve RSS news items mainly due to three reasons: 1) RSS is text rich and its content is dependent on the wording and verbification of the author, thus semantic aware operators are needed; 2) news items are dynamic and consequently time oriented retrieval is needed; 3) a news item may evolve through time, or overlap with other news items and hence identifying relationships between items is also needed. In this paper, we aim to solve these issues by providing a dedicated RSS algebra based on semantic-aware operators that consider RSS characteristics. The provided operators are application domain specific and …
Topological properties of cellular automata on trees
2012
We prove that there do not exist positively expansive cellular automata defined on the full k-ary tree shift (for k>=2). Moreover, we investigate some topological properties of these automata and their relationships, namely permutivity, surjectivity, preinjectivity, right-closingness and openness.
OntoVersionGraph : a change management methodology dedicated to formal ontologies and their user views in a collaborative context
2014
The world changes over time, impacting the knowledge of every subdomain it contains. Therefore systems describing the knowledge of a certain domain should be able to consider changes occurred to keep its knowledge representation up-to-date. Formal ontologies are one of them: they explicitly and formally represent the knowledge of a domain in all its forms and modes of existence. Collaboratively developed, a formal ontology allows the domain users to understand each other by sharing the same terminology despite the different assumptions they have on the domain conceptualization. However, due to its completeness, the complexity of its conceptualization can sometimes make the domain knowledge …
Asymptotic bit frequency in Fibonacci words
2021
It is known that binary words containing no $k$ consecutive 1s are enumerated by $k$-step Fibonacci numbers. In this note we discuss the expected value of a random bit in a random word of length $n$ having this property.
On the suffix automaton with mismatches
2007
International audience; In this paper we focus on the construction of the minimal deterministic finite automaton S_k that recognizes the set of suffixes of a word w up to k errors. We present an algorithm that makes use of S_k in order to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r, where r is the value of the repetition index of w. Moreover, we give some experimental results on some well-known words, like prefixes of Fibonacci and Thue-Morse words, and we make a conjecture on the size of the suffix automaton with mismatches.
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.