Intersection of regular languages and star hierarchy

DOI10.1007/3-540-45465-9_15MaRDI QIDQ4737154zbMATH OpenFDO

Authors Sebastian Bala

Publication date 11 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2380/23800159.htm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Recommendations

• A logical approach to decidability of hierarchies of regular star-free languages
• On theory of regular languages with the Kleene star operation
• Regular languages of star height one
• State complexity of union and intersection of star on \(k\) regular languages
• scientific article; zbMATH DE number 1534571
• Intersection and union of regular languages and state complexity
• APPROXIMATING DEPENDENCY GRAMMARS THROUGH INTERSECTION OF STAR-FREE REGULAR LANGUAGES
• scientific article; zbMATH DE number 1396734
• Decidable hierarchies of starfree languages
• Star-connected flat languages and automata

Cited in

(17)

• A characterization of rational star languages generated by strong codes
• The infinite 2-star height hierarchy of extended regular languages of star degree at most two
• Deciding regular intersection emptiness of complete problems for PSPACE and the polynomial hierarchy
• Binary intersection revisited
• Binary intersection formalized
• A logical approach to decidability of hierarchies of regular star-free languages
• Regular expression star-freeness is PSPACE-complete
• Regular languages of star height one
• On the complexity of intersecting regular, context-free, and tree languages
• The complexity of intersecting finite automata having few final states
• Characterization of Star-Connected Languages Using Finite Automata
• The membership problem for regular expressions with intersection is complete in LOGCFL
• The emptiness problem for intersections of regular languages
• APPROXIMATING DEPENDENCY GRAMMARS THROUGH INTERSECTION OF STAR-FREE REGULAR LANGUAGES
• The language intersection problem for non-recursive context-free grammars
• On the complexity of intersection non-emptiness for star-free language classes
• Incremental algorithms for solving regular expression intersection non-emptiness

This page was built for publication: Intersection of regular languages and star hierarchy

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