SHRINKING RESTARTING AUTOMATA

DOI10.1142/S0129054107004723zbMATH Open1112.68087OpenAlexW2067373940MaRDI QIDQ3434280FDOQ3434280

Authors: Tomasz Jurdziński, Friedrich Otto 

Publication date: 25 April 2007

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054107004723

Recommendations

• Mathematical Foundations of Computer Science 2005
• Restarting automata with restricted utilization of auxiliary symbols
• scientific article; zbMATH DE number 2040896
• On the complexity of 2-monotone restarting automata
• Restarting Tree Automata

zbMATH Keywords

simulationclosure propertiesrestarting automatonlanguage classes

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Title not available (Why is that?)
• Growing context-sensitive languages and Church-Rosser languages
• Quasi-realtime languages
• Membership for growing context-sensitive grammars is polynomial
• Church-Rosser Thue systems and formal languages
• Time-bounded grammars and their languages

Cited In (22)

• Restarting tiling automata
• ON THE POWER OF RRWW-AUTOMATA
• A Complete Taxonomy of Restarting Automata without Auxiliary Symbols*
• A hierarchy of transducing observer systems
• Title not available (Why is that?)
• On the complexity of 2-monotone restarting automata
• On CD-systems of stateless deterministic R-automata with window size one
• Shrinking timed automata
• Power of S-\(k\)R-RRWW-automata
• On restarting automata with auxiliary symbols and small window size
• Left-to-right regular languages and two-way restarting automata
• Mathematical Foundations of Computer Science 2005
• On restarting automata with window size one
• On h-lexicalized restarting list automata
• Fundamentals of Computation Theory
• Two-dimensional hierarchies of proper languages of lexicalized FRR-automata
• On Ordered RRWW-Automata
• Title not available (Why is that?)
• A hierarchy of monotone deterministic non-forgetting restarting automata
• On deterministic ordered restart-delete automata
• Regulated variants of limited context restarting automata
• COOPERATING DISTRIBUTED SYSTEMS OF RESTARTING AUTOMATA

This page was built for publication: SHRINKING RESTARTING AUTOMATA

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3434280)