On the descriptional complexity of stateless deterministic ordered restarting automata

DOI10.1016/j.ic.2017.09.006zbMath1390.68412OpenAlexW2753025899MaRDI QIDQ1706159

Publication date: 21 March 2018

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

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

zbMATH Keywords

decision problems rational functions descriptional complexity restarting automaton language operations transductions ordered rewriting

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items (3)

On the expressive power of stateless ordered restart-delete automata ⋮ On deterministic ordered restart-delete automata ⋮ Reversibility for stateless ordered RRWW-automata

Uses Software

LANGAGE

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Restarting transducers, regular languages, and rational relations
Deterministic ordered restarting automata for picture languages
Succinct description of regular languages by weak restarting automata
More concise representation of regular languages by automata and regular expressions
Intersection and union of regular languages and state complexity
Space-bounded reducibility among combinatorial problems
The state complexities of some basic operations on regular languages
Families of locally testable languages
Determination of finite automata accepting subregular languages
Relationships between nondeterministic and deterministic tape complexities
Locally testable languages
On the Effects of Nondeterminism on Ordered Restarting Automata
Reversible Ordered Restarting Automata
Characterizing the Rational Functions by Restarting Transducers
In Search of Most Complex Regular Languages
Ordered Restarting Automata for Picture Languages
Deterministic Ordered Restarting Automata that Compute Functions
Properties of Finite and Pushdown Transducers
Alternation
Bounded-crossing transducers
MSO definable string transductions and two-way finite-state transducers
Algebraic decision procedures for local testability
Characterizing the Regular Languages by Nonforgetting Restarting Automata
State-complexity of finite-state devices, state compressibility and incompressibility
Weight-Reducing Hennie Machines and Their Descriptional Complexity
On the Descriptional Complexity of Deterministic Ordered Restarting Automata
On Some Decision Problems for Stateless Deterministic Ordered Restarting Automata
On Relations Defined by Generalized Finite Automata
One-tape, off-line Turing machine computations

This page was built for publication: On the descriptional complexity of stateless deterministic ordered restarting automata