Stack Exchange Network

Stack Exchange network consists of 176 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Loading…
  1. 0
  2. +0
    • Tour Start here for a quick overview of the site
    • Help Center Detailed answers to any questions you might have
    • Meta Discuss the workings and policies of this site
    • About Us Learn more about Stack Overflow the company
    • Business Learn more about hiring developers or posting ads with us
  3. Log in Sign up
  4. current community

    • Computer Science
      help chat
    • Computer Science Meta

    your communities

    Sign up or log in to customize your list.

    more stack exchange communities

    company blog
Computer Science
  1. Home
    1. Questions
    2. Tags
    3. Users
    4. Unanswered
    5. Jobs
Profile Activity
Meta user
Network profile
Hermann Gruber

Reputation

357
  • 357
  • 229
  • 101
  • 2018
  • 2019
  • 2020
  • 2021

Top tag

complexity-theory

Next privilege

500 Rep.
Access review queues

Badges

2
9

Newest

 Civic Duty

Next badge

0/1
Critic

Impact

~3k
people reached
5 posts edited
1 helpful flag
359 votes cast
Summary Answers Questions Tags Badges Bookmarks Bounties Reputation All actions

21 Bookmarks

Votes Activity Newest Views Added
29
votes
2
answers
2k
views

Longest Repeated (Scattered) Subsequence in a String

algorithms complexity-theory np-complete strings subsequences
Oct 4 at 9:23 pcpthm 96
29
votes
1
answer
875
views

Graph problem known to be $NP$-complete only under Cook reduction

complexity-theory graphs np-complete reductions
Jan 29 '20 at 11:34 Hermann Gruber 357
29
votes
11
answers
4k
views

Unusual applications of regular expressions?

regular-expressions
May 9 at 8:26 Michael Zedeler 121
28
votes
1
answer
2k
views

Is regex golf NP-Complete?

complexity-theory np-complete regular-expressions
Jan 22 '14 at 0:39 FrankW 6,471
26
votes
1
answer
775
views

“Dense” regular expressions generate $\Sigma^*$?

formal-languages regular-languages regular-expressions
Dec 19 '12 at 21:45 Yuval Filmus 246k
24
votes
4
answers
1k
views

Do undecidable languages exist in constructivist logic?

formal-languages turing-machines logic proof-techniques undecidability
Sep 29 '16 at 18:00 jmite 28.2k
11
votes
3
answers
2k
views

Why are regular expressions defined with union, concatenation and star operations?

formal-languages regular-languages regular-expressions
Jan 30 '20 at 21:21 reinierpost 4,015
7
votes
1
answer
154
views

Non-deterministic Büchi vs Rabin: Automaton size for LTL->automaton

automata linear-temporal-logic
Dec 31 at 23:27 D.W.♦ 129k
6
votes
0
answers
699
views

Minimal regular expression that matches a given set of words

optimization regular-expressions strings exact-string-matching
Nov 18 '19 at 16:08 siracusa 305
5
votes
0
answers
122
views

Is there a polynomial-time algorithm to minimize regular expressions without Kleene closures/stars?

regular-expressions complexity-classes finite-sets
Sep 23 '19 at 23:58 Patrick87 12.3k
5
votes
1
answer
292
views

Who invented the state elimination algorithm for converting finite automata into regular expressions?

reference-request finite-automata regular-expressions
May 22 '15 at 8:58 Hendrik Jan 24.7k
5
votes
1
answer
354
views

What is the complexity of finding a regular expression equivalent to a given DFA?

complexity-theory finite-automata regular-expressions search-problem
Sep 17 '15 at 16:19 Community♦ 1
5
votes
1
answer
96
views

Primitive word and cyclic rotations

strings word-combinatorics
Jan 17 '20 at 21:14 Hermann Gruber 357
4
votes
1
answer
780
views

Cartesian product of regular expressions?

finite-automata regular-expressions
Mar 7 '18 at 3:53 Yuval Filmus 246k
4
votes
1
answer
2k
views

Proving that the scramble of a regular language is context-free

formal-languages regular-languages context-free
Apr 7 '16 at 0:18 Vim 143
4
votes
1
answer
101
views

Origin of “Cookie” in Computing?

terminology history
Sep 21 at 20:43 Hermann Gruber 357
3
votes
1
answer
116
views

Why Study Complexity Theory?

complexity-theory asymptotics
Sep 9 at 4:22 D.W.♦ 129k
3
votes
0
answers
53
views

Minimal regular expression from minimal NFA for finite language in polynomial time?

finite-automata regular-expressions nondeterminism finite-sets
Sep 24 '19 at 0:12 Patrick87 12.3k
1
vote
1
answer
34
views

Size, depth, and time of circuits

complexity-theory
Jan 3 '20 at 18:44 D.W.♦ 129k
1
vote
1
answer
88
views

Is every linear language in NL?

complexity-theory context-free space-complexity complexity-classes
Jun 7 at 11:43 frenkie21 13
1
vote
0
answers
223
views

Number of non deterministic finite automata that can be constructed for $n$ states and alphabet with $m$ symbols

formal-languages automata finite-automata
Jun 24 '18 at 19:02 anir 1,417
Computer Science
  • Tour
  • Help
  • Chat
  • Contact
  • Feedback
  • Mobile
Company
  • Stack Overflow
  • For Teams
  • Advertise With Us
  • Hire a Developer
  • Developer Jobs
  • About
  • Press
  • Legal
  • Privacy Policy
  • Terms of Service
Stack Exchange
Network
  • Technology
  • Life / Arts
  • Culture / Recreation
  • Science
  • Other
  • Stack Overflow
  • Server Fault
  • Super User
  • Web Applications
  • Ask Ubuntu
  • Webmasters
  • Game Development
  • TeX - LaTeX
  • Software Engineering
  • Unix & Linux
  • Ask Different (Apple)
  • WordPress Development
  • Geographic Information Systems
  • Electrical Engineering
  • Android Enthusiasts
  • Information Security
  • Database Administrators
  • Drupal Answers
  • SharePoint
  • User Experience
  • Mathematica
  • Salesforce
  • ExpressionEngine® Answers
  • Stack Overflow em Português
  • Blender
  • Network Engineering
  • Cryptography
  • Code Review
  • Magento
  • Software Recommendations
  • Signal Processing
  • Emacs
  • Raspberry Pi
  • Stack Overflow на русском
  • Code Golf
  • Stack Overflow en español
  • Ethereum
  • Data Science
  • Arduino
  • Bitcoin
  • Software Quality Assurance & Testing
  • Sound Design
  • Windows Phone
  • more (28)
  • Photography
  • Science Fiction & Fantasy
  • Graphic Design
  • Movies & TV
  • Music: Practice & Theory
  • Worldbuilding
  • Video Production
  • Seasoned Advice (cooking)
  • Home Improvement
  • Personal Finance & Money
  • Academia
  • Law
  • Physical Fitness
  • Gardening & Landscaping
  • Parenting
  • more (10)
  • English Language & Usage
  • Skeptics
  • Mi Yodeya (Judaism)
  • Travel
  • Christianity
  • English Language Learners
  • Japanese Language
  • Chinese Language
  • French Language
  • German Language
  • Biblical Hermeneutics
  • History
  • Spanish Language
  • Islam
  • Русский язык
  • Russian Language
  • Arqade (gaming)
  • Bicycles
  • Role-playing Games
  • Anime & Manga
  • Puzzling
  • Motor Vehicle Maintenance & Repair
  • Board & Card Games
  • Bricks
  • Homebrewing
  • Martial Arts
  • The Great Outdoors
  • Poker
  • Chess
  • Sports
  • more (16)
  • MathOverflow
  • Mathematics
  • Cross Validated (stats)
  • Theoretical Computer Science
  • Physics
  • Chemistry
  • Biology
  • Computer Science
  • Philosophy
  • Linguistics
  • Psychology & Neuroscience
  • Computational Science
  • more (10)
  • Meta Stack Exchange
  • Stack Apps
  • API
  • Data
  • Blog
  • Facebook
  • Twitter
  • LinkedIn
  • Instagram

site design / logo © 2021 Stack Exchange Inc; user contributions licensed under cc by-sa. rev 2021.3.5.38718