On simple representations of language families
K. Culik II, H. A. Maurer (1979)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Displaying similar documents to “Rebootable and suffix-closed -power languages”
On simple representations of language families
Fair expressions and regular languages over lists
L. Breveglieri (1997)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
A note on the undecidability of contextfreeness
J. Albert (1982)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
On the expressive power of the shuffle operator matched with intersection by regular sets
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. ...
On languages satisfying “interchange Lemma”
Victor Mitrana (1993)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Disjunctive languages and compatible orders
M. Ito, H. J. Shyr, G. Thierrin (1989)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Consensual languages and matching finite-state computations
Stefano Crespi Reghizzi, Pierluigi San Pietro (2011)
RAIRO - Theoretical Informatics and Applications
Similarity:
An ever present, common sense idea in language modelling research is that, for a word to be a valid phrase, it should comply with multiple constraints at once. A new language definition model is studied, based on agreement or consensus between similar strings. Considering a regular set of strings over a bipartite alphabet made by pairs of unmarked/marked symbols, a match relation is introduced, in order to specify when such strings agree. Then a regular set over the bipartite alphabet...
Consensual languages and matching finite-state computations
Stefano Crespi Reghizzi, Pierluigi San Pietro (2011)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
An ever present, common sense idea in language modelling research is that, for a word to be a valid phrase, it should comply with multiple constraints at once. A new language definition model is studied, based on agreement or consensus between similar strings. Considering a regular set of strings over a bipartite alphabet made by pairs of unmarked/marked symbols, a match relation is introduced, in order to specify when such strings agree. Then a regular set over the bipartite alphabet...