Descriptional complexity of bounded regular languages

DOI10.1007/978-3-319-41114-9_11MaRDI QIDQ2829978zbMATH OpenOpenAlexFDO

Authors Andrea Herrmann, Martin Kutrib, Andreas Malcher, Matthias Wendlandt

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)

Recommendations

• Descriptional complexity of bounded regular languages
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Concatenation of regular languages and descriptional complexity
• Descriptional complexity of regular languages
• State complexity of regular languages

Cites work

• A lower bound technique for the size of nondeterministic finite automata
• A survey on operational state complexity
• Bounded Regular Sets
• CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
• Descriptional complexity of bounded context-free languages
• Determination of finite automata accepting subregular languages
• Finite automata and unary languages
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1016990 (Why is no real title available?)
• scientific article; zbMATH DE number 1156489 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• Intersection and union of regular languages and state complexity
• On bounded languages and reversal-bounded automata
• Regularity and Related Problems for Deterministic Pushdown Automata
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• State complexity of regular languages
• Succinct representation of regular languages by Boolean automata
• The state complexities of some basic operations on regular languages
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION

Cited in

(6)

• Determination of finite automata accepting subregular languages
• Concatenation of Regular Languages and Descriptional Complexity
• scientific article; zbMATH DE number 4049104 (Why is no real title available?)
• Descriptional complexity of bounded regular languages
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• scientific article; zbMATH DE number 7770053 (Why is no real title available?)

This page was built for publication: Descriptional complexity of bounded regular languages

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