Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/111145
Title: Polynomial Languages with Finite Antidictionaries
Authors: Shur, A. M.
Issue Date: 2009
Publisher: EDP Sciences
Citation: Shur A. M. Polynomial Languages with Finite Antidictionaries / A. M. Shur // RAIRO - Theoretical Informatics and Applications. — 2009. — Vol. 43. — Iss. 2. — P. 269-279.
Abstract: We tackle the problem of studying which kind of functions can occur as complexity functions of formal languages of a certain type. We prove that an important narrow subclass of rational languages contains languages of polynomial complexity of any integer degree over any non-trivial alphabet. © 2008 EDP Sciences.
Keywords: COMBINATORIAL COMPLEXITY
FINITE ANTIDICTIONARY
REGULAR LANGUAGE
WED-LIKE AUTOMATON
ANTIDICTIONARIES
COMBINATORIAL COMPLEXITY
FINITE ANTIDICTIONARY
NON-TRIVIAL
POLYNOMIAL COMPLEXITY
RATIONAL LANGUAGES
REGULAR LANGUAGE
WED-LIKE AUTOMATON
FORMAL LANGUAGES
QUERY LANGUAGES
TRANSLATION (LANGUAGES)
LINGUISTICS
URI: http://hdl.handle.net/10995/111145
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 67949092568
ISSN: 0988-3754
metadata.dc.description.sponsorship: The author is grateful to O. Karyakina for the idea of the web-like automaton. Special thanks to J. Karhum¨aki and to the referee for valuable remarks on the paper.
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-67949092568.pdf169,57 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.