Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Article type: Research Article
Authors: Cojocaru, Liliana | Mรคkinen, Erkki
Affiliations: School of Information Sciences, Computer Science, University of Tampere, Kanslerinrinne 1, Tampere, FIN-33014, Finland. {Liliana.Cojocaru, Erkki.Makinen}@uta.fi
Note: [] Address for correspondence: School of Information Sciences, Computer Science, University of Tampere, Kanslerinrinne 1, Tampere, FIN-33014, Finland
Abstract: The regulated rewriting mechanism is one of the most efficient methods to augment the Chomsky hierarchy with a large variety of language classes. In this paper we investigate the derivation mechanism in regulated rewriting grammars such as matrix grammars, by studying their Szilard languages. We focus on the complexity of Szilard languages associated with unrestricted and leftmost-like derivations in matrix grammars, with or without appearance checking. The reason is twofold. First, to relate these classes of languages to parallel complexity classes such as ๐ฉ๐1 and ๐๐1, and, second, to improve some previous results. We prove that unrestricted Szilard languages and certain leftmost Szilard languages of context-free matrix grammars, without appearance checking, can be accepted by indexing alternating Turing machines in logarithmic time and space. Consequently, these classes are included in UE*-uniform ๐ฉ๐1. Unrestricted Szilard languages of matrix grammars with appearance checking can be accepted by deterministic Turing machines in ๐ช(n log n) time and ๐ช(log n) space. Leftmost-like Szilard languages of context-free matrix grammars, with appearance checking, can be recognized by nondeterministic Turing machines by using the same time and space resources. Hence, all these classes are included in ๐๐1.
Keywords: matrix grammars, Szilard languages, (alternating) Turing machines, ๐ฉ๐^{1} and ๐๐^{1} complexity classes
DOI: 10.3233/FI-2013-817
Journal: Fundamenta Informaticae, vol. 123, no. 4, pp. 381-399, 2013
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
ๅฆๆๆจๅจๅบ็ๆน้ข้่ฆๅธฎๅฉๆๆไปปไฝๅปบ, ไปถ่ณ: editorial@iospress.nl