Languajes and monoids with disjuntive identity.
Lila Kari, Gabriel Thierrin (1995)
Collectanea Mathematica
Similarity:
Lila Kari, Gabriel Thierrin (1995)
Collectanea Mathematica
Similarity:
Janusz A. Brzozowski (1974-1975)
Séminaire Dubreil. Algèbre et théorie des nombres
Similarity:
Ondřej Klíma, Libor Polák (2008)
RAIRO - Theoretical Informatics and Applications
Similarity:
A language is literally idempotent in case that if and only if , for each , . Varieties of literally idempotent languages result naturally by taking all literally idempotent languages in a classical (positive) variety or by considering a certain closure operator on classes of languages. We initiate the systematic study of such varieties. Various classes of literally idempotent languages can be characterized using syntactic methods. A starting example is the class of all finite unions...
Joanna Jȩdrzejowicz, Andrzej Szepietowski (2001)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We investigate the complexity of languages described by some expressions containing shuffle operator and intersection. We show that deciding whether the shuffle of two words has a nonempty intersection with a regular set (or fulfills some regular pattern) is NL-complete. Furthermore we show that the class of languages of the form , with a shuffle language and a regular language , contains non-semilinear languages and does not form a family of mildly context- sensitive languages. ...
Janusz A. Brzozowski (1976)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Mikulášek, Karel (1996)
Mathematica Pannonica
Similarity:
Volker Diekert, Axel Möbus (1989)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Henning Bordihn, Jürgen Dassow, Markus Holzer (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We define H- and EH-expressions as extensions of regular expressions by adding homomorphic and iterated homomorphic replacement as new operations, resp. The definition is analogous to the extension given by Gruska in order to characterize context-free languages. We compare the families of languages obtained by these extensions with the families of regular, linear context-free, context-free, and EDT0L languages. Moreover, relations to language families based on patterns, multi-patterns,...