article

Some results on RWW- and RRWW-automata and their relation to the class of growing context-sensitive languages

Authors:

Tomasz Jurdziński,

Krzysztof Lorys,

Gundula Niemann,

Friedrich OttoAuthors Info & Claims

Journal of Automata, Languages and Combinatorics, Volume 9, Issue 4

Pages 407 - 437

Published: 01 October 2004 Publication History

Abstract

It is shown that already the RWW-automata of Jancar et al (1998) accept the Gladkij language L_G1 = {w#w^R#w | w {a, b}^*}, which implies that the class GCSL of growing context-sensitive languages is a proper subclass of the class L(RWW) of languages accepted by the RWW-automata. In addition, it is shown that L(RWW) contains an NP-complete language. Also a simple reduction from the class L(RRWW) of languages accepted by the RRWW-automata to the class L(RWW) is presented, which indicates that these two classes will be hard to separate if they are not identical. Finally, characterizations of the class GCSL in terms of restricted versions of the RWW- and the RRWW-automata are given.

References

[1]

{1} G. BUNTROCK, Wachsende kontext-sensitive Sprachen. Habilitationsschrift, Fakultät für Mathematik und Informatik, Universität Würzburg, July 1996.

[2]

{2} G. BUNTROCK, F. OTTO, Growing context-sensitive languages and Church-Rosser languages. Information and Computation 141 (1998) 1-36.

Digital Library

[3]

{3} E. DAHLHAUS, M. WARMUTH, Membership for growing context-sensitive grammars is polynomial. Journal of Computer and System Sciences 33 (1986) 456-472.

Digital Library

[4]

{4} M.R. GAREY, D.S. JOHNSON, Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979.

Digital Library

[5]

{5} J.E. HOPCROFT, J.D. ULLMAN, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, M.A., 1979.

Digital Library

[6]

{6} P. JANČAR, F. MRÁz, M. PLÁTEK, J. VOGEL, Restarting autamata. In: H. REICHEL (ed.), Fundamentals of Computation Theory, Proceedings FCT'95, Lecture Notes in Computer Science 965, pages 283-292. Springer-Verlag, Berlin, 1995.

Digital Library

[7]

{7} P. JANČAR, F. MRÁZ, M. PLÁTEK, J. VOGEL, On restarting automata with rewriting. In: G. PAUN, A. SALOMAA (eds.), New Trends in Formal Languages, Lecture Notes in Computer Science 1218, pages 119-136. Springer-Verlag, Berlin, 1997.

Digital Library

[8]

{8} P. JANČAR, F. MRÁZ, M. PLÁTEK, J. VOGEL, Different types of monotonicity for restarting automata. In: V. ARVIND, R. RAMANUJAM (eds.), Foundations of Software Technology and Theoretical Computer Science, 18th Conference, Proceedings, Lecture Notes in Computer Science 1530, pages 343-354. Springer-Verlag, Berlin, 1998.

Digital Library

[9]

{9} P. JANČAR, F. MRÁZ, M. PLÁTEK, J. VOGEL, On monotonic automata with a restart operation. Journal of Automata, Languages, and Combinatorics 4 (1999) 287-311.

Digital Library

[10]

{10} R. MCNAUGHTON, P. NARENDRAN, F. OTTO, Church-Rosser Thue systems and formal languages. Journal of the Association for Computing Machinery 35 (1988) 324-344.

Digital Library

[11]

{11} P. NARENDRAN, Church-Rosser and Related Thue Systems. PhD dissertation, Rensselaer Polytechnic Institute, Troy, New York, 1984.

Digital Library

[12]

{12} G. NIEMANN, Church-Rosser Languages and Related Classes. Doctoral dissertation, Fachbereich Mathematik/Informatik, Universität Kassel, 2002.

[13]

{13} G. NIEMANN, F. OTTO, The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. In: M. NIVAT (ed.), Foundations of Software Science and Computation Structures, Proceedings FoSSaCS'98, Lecture Notes in Computer Science 1378, pages 243-257. Springer-Verlag, Berlin, 1998.

Digital Library

[14]

{14} G. NIEMANN, F. OTTO, Restarting automata, Church-Rosser languages, and representations of r.e. languages. In: G. ROZENBERG, W. THOMAS (eds.), Developments in Language Theory - Foundations, Applications, and Perspectives, Proceedings DLT 1999, pages 103-114. World Scientific, Singapore, 2000.

[15]

{15} G. NIEMANN, F. OTTO, On the power of RRWW-automata. In: M. ITO, G. PAUN, S. Yu (eds.), Words, Semigroups, and Transductions. Essays in Honour of Gabriel Thierrin, On the Occasion of His 80th Birthday, pages 341-356. World Scientific, Singapore, 2001.

[16]

{16} G. NIEMANN, F. OTTO, Further results on restarting automata. In: M. ITO, T. IMAOKA (eds.), Words, Languages and Combinatorics III, Proceedings, pages 353-369. World Scientific, Singapore, 2003.

[17]

{17} G. NIEMANN, F. OTTO, The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. Information and Computation 197 (2005) 1-21.

Digital Library

Cited By

Otto FWang Q(2018)Weighted restarting automataSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-016-2164-422:4(1067-1083)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s00500-016-2164-4
Kwee KOtto F(2016)On Ordered RRWW-AutomataProceedings of the 20th International Conference on Developments in Language Theory - Volume 984010.1007/978-3-662-53132-7_22(268-279)Online publication date: 25-Jul-2016
https://dl.acm.org/doi/10.1007/978-3-662-53132-7_22
Messerschmidt HOtto F(2008)On determinism versus nondeterminism for restarting automataInformation and Computation10.1016/j.ic.2008.03.021206:9-10(1204-1218)Online publication date: 1-Sep-2008
https://dl.acm.org/doi/10.1016/j.ic.2008.03.021
Show More Cited By

Index Terms

Some results on RWW- and RRWW-automata and their relation to the class of growing context-sensitive languages

Recommendations

A Perfect Class of Context-Sensitive Timed Languages
DLT 2016: Proceedings of the 20th International Conference on Developments in Language Theory - Volume 9840

Perfect languages--a term coined by Esparza, Ganty, and Majumdar--are the classes of languages that are closed under Boolean operations and enjoy decidable emptiness problem. Perfect languages form the basis for decidable automata-theoretic model-...
Limited Automata and Context-Free Languages
Non-Classical Models of Automata and Applications V

Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥ 2, these devices characterize the class of context-free languages. We investigate the equivalence ...
The Boolean Closure of Growing Context-Sensitive Languages

The set of growing context-sensitive languages (GCSL) is a naturally defined subclass of context-sensitive languages whose membership problem is solvable in polynomial time. Moreover, growing context-sensitive languages and their deterministic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Automata, Languages and Combinatorics

Journal of Automata, Languages and Combinatorics Volume 9, Issue 4

October 2004

75 pages

ISSN:1430-189X

Issue’s Table of Contents

Publisher

Otto-von-Guericke-Universitat

Germany

Publication History

Published: 01 October 2004

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Otto FWang Q(2018)Weighted restarting automataSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-016-2164-422:4(1067-1083)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s00500-016-2164-4
Kwee KOtto F(2016)On Ordered RRWW-AutomataProceedings of the 20th International Conference on Developments in Language Theory - Volume 984010.1007/978-3-662-53132-7_22(268-279)Online publication date: 25-Jul-2016
https://dl.acm.org/doi/10.1007/978-3-662-53132-7_22
Messerschmidt HOtto F(2008)On determinism versus nondeterminism for restarting automataInformation and Computation10.1016/j.ic.2008.03.021206:9-10(1204-1218)Online publication date: 1-Sep-2008
https://dl.acm.org/doi/10.1016/j.ic.2008.03.021
Jancar PMráz FPlátek MVogel J(2007)Monotonicity of restarting automataJournal of Automata, Languages and Combinatorics10.5555/1463079.146308112:3(355-371)Online publication date: 1-Jan-2007
https://dl.acm.org/doi/10.5555/1463079.1463081
Stamer HOtto F(2007)Restarting Tree AutomataProceedings of the 33rd conference on Current Trends in Theory and Practice of Computer Science10.1007/978-3-540-69507-3_44(510-521)Online publication date: 20-Jan-2007
https://dl.acm.org/doi/10.1007/978-3-540-69507-3_44
Jurdziński TMráz FOtto FPlátek M(2006)Degrees of non-monotonicity for restarting automataTheoretical Computer Science10.1016/j.tcs.2006.08.029369:1(1-34)Online publication date: 15-Dec-2006
https://dl.acm.org/doi/10.1016/j.tcs.2006.08.029
Jurdzinski TOtto F(2006)Restarting automata with restricted utilization of auxiliary symbolsTheoretical Computer Science10.1016/j.tcs.2006.07.023363:2(162-181)Online publication date: 28-Oct-2006
https://dl.acm.org/doi/10.1016/j.tcs.2006.07.023
Jurdziński TOtto FMráz FPlátek M(2004)On the complexity of 2-monotone restarting automataProceedings of the 8th international conference on Developments in Language Theory10.1007/978-3-540-30550-7_20(237-248)Online publication date: 13-Dec-2004
https://dl.acm.org/doi/10.1007/978-3-540-30550-7_20

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents