Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with formal languages:
TR01-081 | 8th August 2001
Palash Sarkar

Pushdown Automaton with the Ability to Flip its Stack

We introduce the idea of pushdown automata with the ability to flip
its stack. By bounding the number of times the stack can be flipped
we obtain a hierarchy of language classes from the context free
languages to the recursively enumerable languages. We show that each
class in ... more >>>

TR11-035 | 4th March 2011
Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

Typed Monoids -- An Eilenberg-like Theorem for non regular Languages

Based on different concepts to obtain a finer notion of language recognition via finite monoids we develop an algebraic structure called typed monoid.
This leads to an algebraic description of regular and non regular languages.

We obtain for each language a unique minimal recognizing typed monoid, the typed syntactic monoid.
more >>>

ISSN 1433-8092 | Imprint