Search results for "Formal Language"
showing 10 items of 357 documents
The class of languages recognizable by 1-way quantum finite automata is not closed under union
2000
In this paper we develop little further the theory of quantum finite automata (QFA). There are already few properties of QFA known, that deterministic and probabilistic finite automata do not have e.g. they cannot recognize all regular languages. In this paper we show, that class of languages recognizable by QFA is not closed under union, even not under any Boolean operation, where both arguments are significant.
Temporal and spatial analysis to personalise an agent's dynamic belief, desire, and intention profiles
2003
The paper addresses the dynamic belief, desire and intention profiles that can be made of an agent following a particular route, for example through a city. It assumes that location of an agent has effects on his beliefs desires and intentions and that the history of agent’s mobility and observed states in different locations can be used to predict his future states if the location is being permanently observed. A formal spatial route language is introduced. Formal relationships between the intentional notions, and the spatial behaviour of an agent are defined. As an application an information agent architecture for reasoning about the intentions of the customers of a mobile location-based …
Some Remarks on Automata Minimality
2011
It is well known that the minimization problem of deterministic finite automata (DFAs) is related to the indistinguishability notion of states (cf. [HMU00]). Indeed, a well known technique to minimize a DFA, essentially, consists in finding pairs of states that are equivalent (or indistinguishable), namely pairs of states (p,q) such that it is impossible to assert the difference between p and q only by starting in each of the two states and asking whether or not a given input string leads to a final state. Since, in the testing states equivalence, the notion of initial state is irrelevant, some of the main techniques for the minimization of automata, such as Moore’s algorithm [Moo56] and Ho…
Words and Patterns
2002
In this paper some new ideas, problems and results on patterns are proposed. In particular, motivated by questions concerning avoidability, we first study the set of binary patterns that can occur in one infinite binary word, comparing it with the set of factors of the word. This suggests a classification of infinite words in terms of the "difference" between the set of its patterns and the set of its factors. The fact that each factor in an infinite word can give rise to several distinct patterns leads to study the set of patterns of a single finite word. This set, endowed with a natural order relation, defines a poset: we investigate the relationships between the structure of such a poset…
MAC design on real 802.11 devices: From exponential to Moderated Backoff
2016
In this paper we describe how a novel backoff mechanism called Moderated Backoff (MB), recently proposed as a standard extension for 802.11 networks, has been prototyped and experimentally validated on a commercial 802.11 card before being ratified. Indeed, for performance reasons, the time critical operations of MAC protocols, such as the backoff mechanism, are implemented into the card hardware/firmware and cannot be arbitrarily changed by third parties or by manufacturers only for experimental reasons. Our validation has been possible thanks to the availability of the so called Wireless MAC Processor (WMP), a prototype of a novel wireless card architecture in which MAC protocols can be p…
Abelian antipowers in infinite words
2019
Abstract An abelian antipower of order k (or simply an abelian k-antipower) is a concatenation of k consecutive words of the same length having pairwise distinct Parikh vectors. This definition generalizes to the abelian setting the notion of a k-antipower, as introduced in Fici et al. (2018) [7] , that is a concatenation of k pairwise distinct words of the same length. We aim to study whether a word contains abelian k-antipowers for arbitrarily large k. S. Holub proved that all paperfolding words contain abelian powers of every order (Holub, 2013 [8] ). We show that they also contain abelian antipowers of every order.
Uniform, Sobolev extension and quasiconformal circle domains
1991
This paper contributes to the theory of uniform domains and Sobolev extension domains. We present new features of these domains and exhibit numerous relations among them. We examine two types of Sobolev extension domains, demonstrate their equivalence for bounded domains and generalize known sufficient geometric conditions for them. We observe that in the plane essentially all of these domains possess the trait that there is a quasiconformal self-homeomorphism of the extended plane which maps a given domain conformally onto a circle domain. We establish a geometric condition enjoyed by these plane domains which characterizes them among all quasicircle domains having no large and no small bo…
Special factors and the combinatorics of suffix and factor automata
2011
AbstractThe suffix automaton (resp. factor automaton) of a finite word w is the minimal deterministic automaton recognizing the set of suffixes (resp. factors) of w. We study the relationships between the structure of the suffix and factor automata and classical combinatorial parameters related to the special factors of w. We derive formulae for the number of states of these automata. We also characterize the languages LSA and LFA of words having respectively suffix automaton and factor automaton with the minimal possible number of states.
The Shuffle Product: New Research Directions
2015
In this paper we survey some recent researches concerning the shuffle operation that arise both in Formal Languages and in Combinatorics on Words.
Unary Probabilistic and Quantum Automata on Promise Problems
2015
We continue the systematic investigation of probabilistic and quantum finite automata (PFAs and QFAs) on promise problems by focusing on unary languages. We show that bounded-error QFAs are more powerful than PFAs. But, in contrary to the binary problems, the computational powers of Las-Vegas QFAs and bounded-error PFAs are equivalent to deterministic finite automata (DFAs). Lastly, we present a new family of unary promise problems with two parameters such that when fixing one parameter QFAs can be exponentially more succinct than PFAs and when fixing the other parameter PFAs can be exponentially more succinct than DFAs.