Synchronizing automata over nested words

DOI10.1007/978-3-662-49630-5_15MaRDI QIDQ2811343zbMATH OpenOpenAlexFDO

Authors Pavel Martyugin, Mahsa Shirmohammadi, Dmitry Chistikov

Publication date 10 June 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10995/102274

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Synchronizing automata over nested words
• Regular languages of nested words: fixed points, automata, and synchronization
• Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization
• Synchronizing automata with finitely many minimal synchronizing words
• Synchronizing words for weighted and timed automata

Cites work

• scientific article; zbMATH DE number 4205991 (Why is no real title available?)
• scientific article; zbMATH DE number 1033441 (Why is no real title available?)
• scientific article; zbMATH DE number 3354928 (Why is no real title available?)
• A Brief History of Strahler Numbers
• Adding nesting structure to words
• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• Hardness results for intersection non-emptiness
• On Time Versus Space
• On programming of arithmetic operations
• On two Combinatorial Problems Arising from Automata Theory
• Parikh's theorem: a simple and direct automaton construction
• Polynomial complete problems in automata theory
• Reset Sequences for Monotonic Automata
• Synchronization of Pushdown Automata
• Synchronizing Automata and the Černý Conjecture
• Synchronizing words for weighted and timed automata
• The complexity of finding reset words in finite automata
• The space complexity of pebble games on trees

Cited in

(13)

• State complexity of the set of synchronizing words for circular automata and automata over binary alphabets
• Synchronizing automata over nested words
• The complexity of synchronizing Markov decision processes
• Synchronizing words for weighted and timed automata
• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• Synchronization of Pushdown Automata
• scientific article; zbMATH DE number 7376069 (Why is no real title available?)
• Infinite Synchronizing Words for Probabilistic Automata
• Synchronizing finite automata with short reset words
• Slowly synchronizing automata with fixed alphabet size
• Synchronizing data words for register automata
• Regular languages of nested words: fixed points, automata, and synchronization
• Synchronizing Data Words for Register Automata

Describes a project that uses

Uses Software

• OpenNWA

This page was built for publication: Synchronizing automata over nested words

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