Decision problems for convex languages

DOI10.1016/j.ic.2010.11.009zbMath1217.68125MaRDI QIDQ553302

Zhi Xu, Janusz A. Brzozowski, Jeffrey O. Shallit

Publication date: 27 July 2011

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2010.11.009

zbMATH Keywords

complexity; ideal; regular language; finite automaton; prefix-free; suffix-free; convex language

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

Related Items

Complexity of bifix-free regular languages, Complexity of bifix-free regular languages, Syntactic complexity of regular ideals, On the state complexity of closures and interiors of regular languages with subwords and superwords, Problems on finite automata and the exponential time hypothesis, Quotient complexity of closed languages, Syntactic complexity of suffix-free languages, Checking Whether an Automaton Is Monotonic Is NP-complete, Decision Problems for Convex Languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On NFAs where all states are final, initial, or both
• Space-bounded reducibility among combinatorial problems
• A note on multiple-entry finite automata
• Some remarks on multiple-entry finite automata
• Multiple-entry finite automata
• Decision Problems for Convex Languages
• Relations on free monoids, their independent sets, and codes¹
• Computational Parallels between the Regular and Context-Free Languages
• Morphisms preserving densities
• Hypercodes
• INFIX-FREE REGULAR EXPRESSIONS AND LANGUAGES
• Ultimate-Definite and Symmetric-Definite Events and Automata
• On free monoids partially ordered by embedding
• Depth-First Search and Linear Graph Algorithms