Marcus t-contextual grammars and cut hierarchies and monotonicity for restarting automata

详细信息    查看全文

• 作者：F. Mrá ; z ; F. Otto ; M. Plá ; tek and T. Jurdziń ; ski
• 关键词：Contextual grammar ; Restarting automaton ; Cut-index ; Monotonicity
• 刊名：Theoretical Computer Science
• 出版年：2006
• 出版时间：20 November 2006
• 年：2006
• 卷：366
• 期：3
• 页码：272-296
• 全文大小：423 K

文摘

The T6GW2-5&_mathId=mml2&_user=10&_cdi=5674&_rdoc=7&_handle=V-WA-A-W-E-MsSAYZW-UUW-U-AAZCWADYEW-AAZWDEYZEW-VWUZDVCC-E-U&_acct=C000050221&_version=1&_userid=10&md5=6db3ff1ce2302f652be26c5d781068d9"" title=""Click to view the MathML source"">t-contextual grammars are generalizations of Marcus contextual grammars, which insert t contexts in each derivation step. If the selection mappings are regular and satisfy an additional locality restriction, then these grammars correspond in their expressive power to restarting automata with cut-index t. In the first part of the paper classes of languages are studied that are accepted by certain types of restarting automata with limited cut-index. As already R-automata with cut-index 1 accept NP-complete languages, additional restrictions in the form of certain monotonicity conditions are also considered. Without the locality restriction c9c7d1409"" title=""Click to view the MathML source"">t-contextual grammars with regular selection correspond to t-RR-automata with cut-index one. These are RR-automata that are allowed to perform up to t deletion operations in each cycle that each delete a single factor only. In the second part of the paper the expressive power of these automata is studied, where the focus is on the special case that certain monotonicity conditions are satisfied.