Search results for "regular language"
showing 10 items of 54 documents
Sur les Codes ZigZag et Leur Décidabilité
1990
AbstractThis paper deals with zigzag factorizations and zigzag codes. The language of “zigzag” over a regular language is represented by constructing a special family of two-way automata. Decidability of zigzag codes, previously shown for the finite languages, is proved here for all regular languages by the analysis of the set of “crossing sequences” produced by a two-way automation in the family. We also obtain that it is decidable whether or not a two-way automation of a certain type is non-ambiguous.RésuméDans ce papier on reprend les notions de factorisation zigzag et de code zigzag. On construit pour tout langage rationnel, une famille d'automates bilatéres lesquels reconnaissent les m…
On the Class of Languages Recognizable by 1-Way Quantum Finite Automata
2007
It is an open problem to characterize the class of languages recognized by quantum finite automata (QFA). We examine some necessary and some sufficient conditions for a (regular) language to be recognizable by a QFA. For a subclass of regular languages we get a condition which is necessary and sufficient. Also, we prove that the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation where both arguments are significant.
CODING PARTITIONS OF REGULAR SETS
2009
A coding partition of a set of words partitions this set into classes such that whenever a sequence, of minimal length, has two distinct factorizations, the words of these factorizations belong to the same class. The canonical coding partition is the finest coding partition that partitions the set of words in at most one unambiguous class and other classes that localize the ambiguities in the factorizations of finite sequences. We prove that the canonical coding partition of a regular set contains a finite number of regular classes and we give an algorithm for computing this partition. From this we derive a canonical decomposition of a regular monoid into a free product of finitely many re…
Quantum Pushdown Automata
2000
Quantum finite automata, as well as quantum pushdown automata were first introduced by C. Moore, J. P. Crutchfield [13]. In this paper we introduce the notion of quantum pushdown automata (QPA) in a non-equivalent way, including unitarity criteria, by using the definition of quantum finite automata of [11]. It is established that the unitarity criteria of QPA are not equivalent to the corresponding unitarity criteria of quantum Turing machines [4]. We show that QPA can recognize every regular language. Finally we present some simple languages recognized by QPA, two of them are not recognizable by deterministic pushdown automata and one seems to be not recognizable by probabilistic pushdown …
Nonstochastic languages as projections of 2-tape quasideterministic languages
1998
A language L (n) of n-tuples of words which is recognized by a n-tape rational finite-probabilistic automaton with probability 1-e, for arbitrary e > 0, is called quasideterministic. It is proved in [Fr 81], that each rational stochastic language is a projection of a quasideterministic language L (n) of n-tuples of words. Had projections of quasideterministic languages on one tape always been rational stochastic languages, we would have a good characterization of the class of the rational stochastic languages. However we prove the opposite in this paper. A two-tape quasideterministic language exists, the projection of which on the first tape is a nonstochastic language.
Capabilities of Ultrametric Automata with One, Two, and Three States
2016
Ultrametric automata use p-adic numbers to describe the random branching of the process of computation. Previous research has shown that ultrametric automata can have a significant decrease in computing complexity. In this paper we consider the languages that can be recognized by one-way ultrametric automata with one, two, and three states. We also show an example of a promise problem that can be solved by ultrametric integral automaton with three states.
Quantum Finite Multitape Automata
1999
Quantum finite automata were introduced by C. Moore, J. P. Crutchfield [4], and by A. Kondacs and J. Watrous [3]. This notion is not a generalization of the deterministic finite automata. Moreover, in [3] it was proved that not all regular languages can be recognized by quantum finite automata. A. Ambainis and R. Freivalds [1] proved that for some languages quantum finite automata may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite automaton but not by deterministic or probabilistic finite automata. This …
Quantum Computers and Quantum Automata
2000
Quantum computation is a most challenging project involving research both by physicists and computer scientists. The principles of quantum computation differ from the principles of classical computation very much. When quantum computers become available, the public-key cryptography will change radically. It is no exaggeration to assert that building a quantum computer means building a universal code-breaking machine. Quantum finite automata are expected to appear much sooner. They do not generalize deterministic finite automata. Their capabilities are incomparable.
Efficient algorithm for learning simple regular expressions from noisy examples
1994
We present an efficient algorithm for finding approximate repetitions in a given sequence of characters. First, we define a class of simple regular expressions which are of star-height one and do not contain union operations, and a stochastic mutation process of a given length over a string of characters. Then, assuming that a given string of characters is obtained corrupted by the defined mutation process from some long enough word generated by a simple regular expression, we try to restore the expression. We prove that to within some reasonable accuracy it is always possible if the length of the mutation process is bounded comparing to the length of the example. We provide an algorithm by…
Some applications of a theorem of Shirshov to language theory
1983
Some applications of a theorem of Shirshov to language theory are given: characterization of regular languages, characterization of bounded languages, and a sufficient condition for a language to be Parikh-bounded.