1998 | OriginalPaper | Buchkapitel
Different Types of Monotonicity for Restarting Automata
verfasst von : Petr Jančar, František Mráz, Martin Plátek, Jörg Vogel
Erschienen in: Foundations of Software Technology and Theoretical Computer Science
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider several classes of rewriting automata with a restart operation and the monotonicity property of computations by such automata. It leads to three natural definitions of (right) monotonicity of automata. Besides the former monotonicity, two new types, namely a-monotonicity and g-monotonicity, for such automata are introduced. We provide a taxonomy of the relevant language classes, and answer the (un)decidability questions concerning these properties.