Succinct description of regular languages by weak restarting automata

DOI10.1016/J.IC.2008.03.016MaRDI QIDQ948085zbMATH OpenOpenAlexFDO

Authors Martin Kutrib, Jens Reimann

Publication date 8 October 2008

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2008.03.016

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• OPTIMAL SIMULATIONS OF WEAK RESTARTING AUTOMATA
• On the descriptional complexity of deterministic ordered restarting automata
• On the descriptional complexity of stateless deterministic ordered restarting automata
• Reversible Ordered Restarting Automata
• Non-recursive trade-offs for deterministic restarting automata

Cites work

• scientific article; zbMATH DE number 1156489 (Why is no real title available?)
• scientific article; zbMATH DE number 2040896 (Why is no real title available?)
• scientific article; zbMATH DE number 1747447 (Why is no real title available?)
• scientific article; zbMATH DE number 1394484 (Why is no real title available?)
• A lower bound technique for the size of nondeterministic finite automata
• Intersection and union of regular languages and state complexity
• Minimal NFA Problems are Hard
• On the size of parsers and \(\text{LR}(k)\)-grammars
• Partial orders on words, minimal elements of regular languages, and state complexity
• Recent advances in formal languages and applications.
• Restarting automata
• Restarting automata, Church-Rosser languages, and representations of {r. e. \ }languages
• Size/lookahead tradeoff for \(LL(k)\)-grammars
• State complexity of some operations on binary regular languages
• State-complexity of finite-state devices, state compressibility and incompressibility
• THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS

Cited in

(16)

• On Stateless Deterministic Restarting Automata
• On CD-systems of stateless deterministic two-phase RR(1)-automata
• OPTIMAL SIMULATIONS OF WEAK RESTARTING AUTOMATA
• scientific article; zbMATH DE number 7444007 (Why is no real title available?)
• On restarting automata with auxiliary symbols and small window size
• On stateless deterministic restarting automata
• On restarting automata with window size one
• Non-recursive trade-offs for deterministic restarting automata
• Restarting transducers, regular languages, and rational relations
• On the descriptional complexity of deterministic ordered restarting automata
• scientific article; zbMATH DE number 6136496 (Why is no real title available?)
• On the descriptional complexity of the window size for deleting restarting automata
• Descriptional complexity of regular languages
• On the descriptional complexity of stateless deterministic ordered restarting automata
• On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata
• On some decision problems for stateless deterministic ordered restarting automata

This page was built for publication: Succinct description of regular languages by weak restarting automata

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