On the Complexity of Intersecting Regular, Context-Free, and Tree Languages

DOI10.1007/978-3-662-47666-6_33zbMath1440.68163OpenAlexW2232942479MaRDI QIDQ3449493

Michael Wehar, Joseph Swernofsky

Publication date: 4 November 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-47666-6_33

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

A theoretical framework for cardinality-based feature models: the semantics and computational aspects ⋮ Problems on finite automata and the exponential time hypothesis

Cites Work

• On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
• Parametrized complexity theory.
• Emptiness of Multi-pushdown Automata Is 2ETIME-Complete
• An Infinite Automaton Characterization of Double Exponential Time
• Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata
• Alternation
• The emptiness problem for intersections of regular languages
• Hardness Results for Intersection Non-Emptiness
• The tree width of auxiliary storage
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

This page was built for publication: On the Complexity of Intersecting Regular, Context-Free, and Tree Languages