Descriptional Complexity of Bounded Regular Languages

DOI10.1007/978-3-319-41114-9_11zbMath1476.68130OpenAlexW2492691995MaRDI QIDQ2829978

Martin Kutrib, Matthias Wendlandt, Andrea Herrmann, Andreas Malcher

Publication date: 9 November 2016

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

Full work available at URL: https://hal.inria.fr/hal-01633949/file/416473_1_En_11_Chapter.pdf

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptional complexity of bounded context-free languages
• A lower bound technique for the size of nondeterministic finite automata
• On bounded languages and reversal-bounded automata
• Finite automata and unary languages
• Succinct representation of regular languages by Boolean automata
• Intersection and union of regular languages and state complexity
• The state complexities of some basic operations on regular languages
• Determination of finite automata accepting subregular languages
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Regularity and Related Problems for Deterministic Pushdown Automata
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
• Bounded Regular Sets

This page was built for publication: Descriptional Complexity of Bounded Regular Languages