Page 1 Next

Displaying 1 – 20 of 126

Showing per page

A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines

Viliam Geffert, Norbert Popély (2010)

RAIRO - Theoretical Informatics and Applications

We show that one-way Π2-alternating Turing machines cannot accept unary nonregular languages in o(log n) space. This holds for an accept mode of space complexity measure, defined as the worst cost of any accepting computation. This lower bound should be compared with the corresponding bound for one-way Σ2-alternating machines, that are able to accept unary nonregular languages in space O(log log n). Thus, Σ2-alternation is more powerful than Π2-alternation for space bounded one-way machines with...

Automata with modulo counters and nondeterministic counter bounds

Daniel Reidenbach, Markus L. Schmid (2014)


We introduce and investigate Nondeterministically Bounded Modulo Counter Automata (NBMCA), which are two-way multi-head automata that comprise a constant number of modulo counters, where the counter bounds are nondeterministically guessed, and this is the only element of nondeterminism. NBMCA are tailored to recognising those languages that are characterised by the existence of a specific factorisation of their words, e. g., pattern languages. In this work, we subject NBMCA to a theoretically sound...

Automata with two-sided pushdowns defined over free groups generated by reduced alphabets

Petr Blatný, Radek Bidlo, Alexander Meduna (2007)


This paper introduces and discusses a modification of pushdown automata. This modification is based on two-sided pushdowns into which symbols are pushed from both ends. These pushdowns are defined over free groups, not free monoids, and they can be shortened only by the standard group reduction. We demonstrate that these automata characterize the family of recursively enumerable languages even if the free groups are generated by no more than four symbols.

Bidirectional string assembling systems

Martin Kutrib, Matthias Wendlandt (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We introduce and investigate several variants of a bidirectional string assembling system, which is a computational model that generates strings from copies of assembly units. The underlying mechanism is based on two-sided piecewise assembly of a double-stranded sequence of symbols, where the upper and lower strand have to match. The generative capacities and the relative power of the variants are our main interest. In particular, we prove that bidirectional string assembling system generate languages...

Call-by-value solvability

Luca Paolini, Simona Ronchi Della Rocca (1999)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Call-by-value Solvability

Luca Paolini, Simona Ronchi Della Rocca (2010)

RAIRO - Theoretical Informatics and Applications

The notion of solvability in the call-by-value λ-calculus is defined and completely characterized, both from an operational and a logical point of view. The operational characterization is given through a reduction machine, performing the classical β-reduction, according to an innermost strategy. In fact, it turns out that the call-by-value reduction rule is too weak for capturing the solvability property of terms. The logical characterization is given through an intersection type assignment system,...

Circular splicing and regularity

Paola Bonizzoni, Clelia De Felice, Giancarlo Mauri, Rosalba Zizza (2004)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Circular splicing has been very recently introduced to model a specific recombinant behaviour of circular DNA, continuing the investigation initiated with linear splicing. In this paper we restrict our study to the relationship between regular circular languages and languages generated by finite circular splicing systems and provide some results towards a characterization of the intersection between these two classes. We consider the class of languages X * , called here star languages, which are closed...

Currently displaying 1 – 20 of 126

Page 1 Next