Two results on discontinuous input processing

DOI10.1007/978-3-319-41114-9_16MaRDI QIDQ2829983zbMATH OpenOpenAlexFDO

Authors Vojtěch Vorel

Publication date 9 November 2016

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.08642

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: First, we show that universality and other properties of general jumping finite automata are undecidable, which answers a question asked by Meduna and Zemek in 2012. Second, we close the study raised by v{C}erno and Mr'{a}z in 2010 by proving that clearing restarting automata using contexts of size two can accept binary non-context-free languages.

Recommendations

• Two results on discontinuous input processing
• On basic properties of jumping finite automata
• Characterization and complexity results on jumping finite automata
• On double-jumping finite automata and their closure properties
• Operational state complexity and decidability of jumping finite automata

Cites work

• scientific article; zbMATH DE number 4160148 (Why is no real title available?)
• scientific article; zbMATH DE number 3990895 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• Characterization and complexity results on jumping finite automata
• Clearing restarting automata
• Insertion and deletion closure of languages
• Insertion languages
• Jumping finite automata
• Jumping finite automata: characterizations and complexity
• On basic properties of jumping finite automata
• On regularity of context-free languages
• Small size insertion and deletion systems

Cited in

(4)

• On basic properties of jumping finite automata
• Two results on discontinuous input processing
• Characterization and complexity results on jumping finite automata
• On double-jumping finite automata and their closure properties

This page was built for publication: Two results on discontinuous input processing

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