On a class of languages recognizable by probabilistic reversible decide-and-halt automata

We analyze the properties of probabilistic reversible decide-and-halt automata (DH-PRA) and show that there is a strong relationship between DH-PRA and 1-way quantum automata. We show that a general class of regular languages is not recognizable by DH-PRA by proving that two “forbidden” constructions in minimal deterministic automata correspond to languages not recognizable by DH-PRA. The shown class is identical to a class known to be not recognizable by 1-way quantum automata. We also prove that the class of languages recognizable by DH-PRA is not closed under union and other non-trivial Boolean operations.     

Array automata and operations on array languages

Array automata acting on scenes (two dimensional tapes) are defined. The set of scenes accepted by array automata are proved to be equivalent to the set of arrays generated by array grammars. Certain operators like substitution, homomorphic replication and insertion are extended to sets of arrays. These operators yield interesting classes of pictures.     

On the efficient construction of quasi-reversible automata for reversible languages

Quasi-reversible automata is a suitable representation for reversible languages. In this work a method is proposed to obtain such an automaton for any given reversible language represented by its minimal DFA. Our method runs in polynomial time respect to the size of the minimal DFA and improves a previous exponential method. Previous bound for the size of quasi-reversible automata is also reduced.     

Feedback automata and their languages

We introduce families of languages which are generated by deterministic and nondeterministic feedback-controlled models of automata. In case of the two deterministic models considered, the generated families are proper subclasses of the family of regular languages, where, in case of the nondeterministic model, the generated family equals the family of ?-free regular languages.     

A computational model for tiling recognizable two-dimensional languages

Tiling systems are a well accepted model to define recognizable two-dimensional languages but they are not an effective device for recognition unless a scanning strategy for the pictures is fixed. We define a tiling automaton as a tiling system equipped with a scanning strategy and a suitable data structure. The class of languages accepted by tiling automata coincides with the REC family. In this framework it is possible to define determinism, non-determinism and unambiguity. Then (deterministic) tiling automata are compared with the other known (deterministic) automata models for two-dimensional languages.     

Binding-blocking automata

We propose an automaton model called as binding-blocking automaton (BBA). It is a finite state automaton together with the ability to block some symbols and postpone them for reading by the head at a later time. The idea of blocking some symbols from being read by the head and unblocking when the system requires to read is motivated by peptide computing where some parts of peptide sequences are blocked by attaching an antibody with higher affinity and unblocked at a later point by the removal of the appropriate antibody. We study the variants of such systems, analyse the power of each variants and show various hierarchy results involving them. We also define normal-forms of binding-blocking automata for one of its variants and also show that the acceptance power of this variant of BBA is strictly less than that of multi-head finite automata.     

Kernel methods for learning languages

This paper studies a novel paradigm for learning formal languages from positive and negative examples which consists of mapping strings to an appropriate high-dimensional feature space and learning a separating hyperplane in that space. Such mappings can often be represented flexibly with string kernels, with the additional benefit of computational efficiency. The paradigm inspected can thus be viewed as that of using kernel methods for learning languages.     

Interference automata

We propose a computing model, the Two-Way Optical Interference Automata (2OIA), that makes use of the phenomenon of optical interference. We introduce this model to investigate the increase in power, in terms of language recognition, of a classical Deterministic Finite Automaton (DFA) when endowed with the facility of interference. The question is in the spirit of Two-Way Finite Automata With Quantum and Classical States (2QCFA) [A. Ambainis, J. Watrous, Two-way finite automata with quantum and classical states, Theoret. Comput. Sci. 287 (1) (2002) 299–311] wherein the classical DFA is augmented with a quantum component of constant size. We test the power of 2OIA against the languages mentioned in the above paper. We give efficient 2OIA algorithms to recognize languages for which 2QCFA machines have been shown to exist, as well as languages whose status vis-a-vis 2QCFA has been posed as open questions. Having a DFA as a component, it trivially recognizes regular languages. We show that our model can recognize all languages recognized by 1-way deterministic blind counter automata. Finally we show the existence of a language that cannot be recognized by a 2OIA but which can be recognized by an O(n³)$O\left(n^3\right)$ space Turing machine.     

Non-deterministic cellular automata and languages

We summarize results on non-deterministic cellular language acceptors. The non-determinism is regarded as limited resource. For parallel devices, it is natural to bound the non-determinism in time and/or space. Depending on the length of the input, the number of allowed non-deterministic state transitions as well as the number of non-deterministic cells at all is limited. We centre our attention to real-time, linear-time, and unrestricted-time computations and discuss the computational power of these machines. Speed-up results and the possibility to reduce the non-determinism as well as closure properties of languages acceptable with a constant number of non-deterministic transitions are presented. By considering the relations with context-free languages, several relations between the devices in question are implied. We do not prove these results but we merely draw attention to the big picture and some of the main ideas involved, and open problems for further research.     

On pebble automata for data languages with decidable emptiness problem

In this paper we study a subclass of pebble automata (PA) for data languages for which the emptiness problem is decidable. Namely, we show that the emptiness problem for weak 2-pebble automata is decidable, while the same problem for weak 3-pebble automata is undecidable. We also introduce the so-called top view weak PA. Roughly speaking, top view weak PA are weak PA where the equality test is performed only between the data values seen by the two most recently placed pebbles. The emptiness problem for this model is still decidable. It is also robust: alternating, non-deterministic and deterministic top view weak PA have the same recognition power; and are strong enough to accept all data languages expressible in Linear Temporal Logic with the future-time operators, augmented with one register freeze quantifier.