State complexity of union and intersection on graph-walking automata

DOI10.1007/978-3-030-93489-7_11MaRDI QIDQ2096590zbMATH OpenOpenAlexFDO

Authors Olga Martynova, Alexander Okhotin

Publication date 9 November 2022

Full work available at URL https://doi.org/10.1007/978-3-030-93489-7_11

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata
• STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES
• State Complexity of Union and Intersection of Finite Languages
• Intersection and union of regular languages and state complexity
• State complexity of catenation combined with union and intersection
• On the state complexity of star of union and star of intersection
• State complexity of two combined operations: catenation-union and catenation-intersection
• State complexity of transforming graph-walking automata to halting, returning and reversible
• State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages
• State complexity of k-union and k-intersection for prefix-free regular languages

Cites work

• Automata and Labyrinths
• Complement for two-way alternating automata
• Complementing deterministic tree-walking automata
• Complementing two-way finite automata
• Graph exploration by a finite automaton
• Graph-walking automata: from whence they come, and whither they are bound
• Halting space-bounded computations
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Operational state complexity of nested word automata
• Partial orders on words, minimal elements of regular languages, and state complexity
• Reversibility of computations in graph-walking automata
• State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata
• Tight bounds for undirected graph exploration with pebbles and multiple agents
• Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
• Tree-Walking Automata Do Not Recognize All Regular Languages

Cited in

(4)

• Homomorphisms on graph-walking automata
• State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata
• Homomorphisms and inverse homomorphisms on graph-walking automata
• Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs

This page was built for publication: State complexity of union and intersection on graph-walking automata

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