Is there a polynomial time algorithm to tell if an NFA over an unary alphabet is universal?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Given an Nondeterministic Finite State Automaton with $n$ states over an unary alphabet, is there some algorithm to check if the automata is universal in time polynomial in the number of states?
I would not expect this would work over an alphabet of size two or more, since it is PSPACE-complete to check whether a regular expression is universal. However, since regular languages over unary alphabets have nice characterizations, I would expect there would be some way to check the universality of an NFA over an unary alphabet.
algorithms formal-languages finite-automata
asked Sep 25 at 4:07
Agnishom Chattopadhyay
1366
add a comment |Â
up vote
2
down vote
favorite
Given an Nondeterministic Finite State Automaton with $n$ states over an unary alphabet, is there some algorithm to check if the automata is universal in time polynomial in the number of states?
I would not expect this would work over an alphabet of size two or more, since it is PSPACE-complete to check whether a regular expression is universal. However, since regular languages over unary alphabets have nice characterizations, I would expect there would be some way to check the universality of an NFA over an unary alphabet.
algorithms formal-languages finite-automata
asked Sep 25 at 4:07
Agnishom Chattopadhyay
1366
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Given an Nondeterministic Finite State Automaton with $n$ states over an unary alphabet, is there some algorithm to check if the automata is universal in time polynomial in the number of states?
I would not expect this would work over an alphabet of size two or more, since it is PSPACE-complete to check whether a regular expression is universal. However, since regular languages over unary alphabets have nice characterizations, I would expect there would be some way to check the universality of an NFA over an unary alphabet.
algorithms formal-languages finite-automata
asked Sep 25 at 4:07
Agnishom Chattopadhyay
1366
Given an Nondeterministic Finite State Automaton with $n$ states over an unary alphabet, is there some algorithm to check if the automata is universal in time polynomial in the number of states?
I would not expect this would work over an alphabet of size two or more, since it is PSPACE-complete to check whether a regular expression is universal. However, since regular languages over unary alphabets have nice characterizations, I would expect there would be some way to check the universality of an NFA over an unary alphabet.
algorithms formal-languages finite-automata
algorithms formal-languages finite-automata
asked Sep 25 at 4:07
Agnishom Chattopadhyay
1366
asked Sep 25 at 4:07
Agnishom Chattopadhyay
1366
asked Sep 25 at 4:07
Agnishom Chattopadhyay
1366
asked Sep 25 at 4:07
Agnishom Chattopadhyay
1366
asked Sep 25 at 4:07
Agnishom Chattopadhyay
1366
1366
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
Determining whether a unary NFA is universal is coNP-complete, as proved by Stockmeyer and Meyer, Word Problems Requiring Exponential Time. See Gruber and Holzer, Computational Complexity of NFA Minimization for
Finite and Unary Languages, for more results in this vein.
answered Sep 25 at 5:29
Yuval Filmus
183k12171332
Could you please point out which result in the first paper you are refering to?
– Agnishom Chattopadhyay
Sep 26 at 11:43
The first paper is cited in the second paper as containing this classical result. Unfortunately no pointer is given. The main hurdle toward reading the first paper is the antiquated terminology.
– Yuval Filmus
Sep 26 at 15:54
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
Determining whether a unary NFA is universal is coNP-complete, as proved by Stockmeyer and Meyer, Word Problems Requiring Exponential Time. See Gruber and Holzer, Computational Complexity of NFA Minimization for
Finite and Unary Languages, for more results in this vein.
answered Sep 25 at 5:29
Yuval Filmus
183k12171332
Could you please point out which result in the first paper you are refering to?
– Agnishom Chattopadhyay
Sep 26 at 11:43
The first paper is cited in the second paper as containing this classical result. Unfortunately no pointer is given. The main hurdle toward reading the first paper is the antiquated terminology.
– Yuval Filmus
Sep 26 at 15:54
add a comment |Â
up vote
3
down vote
Determining whether a unary NFA is universal is coNP-complete, as proved by Stockmeyer and Meyer, Word Problems Requiring Exponential Time. See Gruber and Holzer, Computational Complexity of NFA Minimization for
Finite and Unary Languages, for more results in this vein.
answered Sep 25 at 5:29
Yuval Filmus
183k12171332
Could you please point out which result in the first paper you are refering to?
– Agnishom Chattopadhyay
Sep 26 at 11:43
The first paper is cited in the second paper as containing this classical result. Unfortunately no pointer is given. The main hurdle toward reading the first paper is the antiquated terminology.
– Yuval Filmus
Sep 26 at 15:54
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Determining whether a unary NFA is universal is coNP-complete, as proved by Stockmeyer and Meyer, Word Problems Requiring Exponential Time. See Gruber and Holzer, Computational Complexity of NFA Minimization for
Finite and Unary Languages, for more results in this vein.
answered Sep 25 at 5:29
Yuval Filmus
183k12171332
Determining whether a unary NFA is universal is coNP-complete, as proved by Stockmeyer and Meyer, Word Problems Requiring Exponential Time. See Gruber and Holzer, Computational Complexity of NFA Minimization for
Finite and Unary Languages, for more results in this vein.
answered Sep 25 at 5:29
Yuval Filmus
183k12171332
answered Sep 25 at 5:29
Yuval Filmus
183k12171332
answered Sep 25 at 5:29
Yuval Filmus
183k12171332
answered Sep 25 at 5:29
Yuval Filmus
183k12171332
183k12171332
Could you please point out which result in the first paper you are refering to?
– Agnishom Chattopadhyay
Sep 26 at 11:43
The first paper is cited in the second paper as containing this classical result. Unfortunately no pointer is given. The main hurdle toward reading the first paper is the antiquated terminology.
– Yuval Filmus
Sep 26 at 15:54
add a comment |Â
Could you please point out which result in the first paper you are refering to?
– Agnishom Chattopadhyay
Sep 26 at 11:43
The first paper is cited in the second paper as containing this classical result. Unfortunately no pointer is given. The main hurdle toward reading the first paper is the antiquated terminology.
– Yuval Filmus
Sep 26 at 15:54
Could you please point out which result in the first paper you are refering to?
– Agnishom Chattopadhyay
Sep 26 at 11:43
Could you please point out which result in the first paper you are refering to?
– Agnishom Chattopadhyay
Sep 26 at 11:43
The first paper is cited in the second paper as containing this classical result. Unfortunately no pointer is given. The main hurdle toward reading the first paper is the antiquated terminology.
– Yuval Filmus
Sep 26 at 15:54
The first paper is cited in the second paper as containing this classical result. Unfortunately no pointer is given. The main hurdle toward reading the first paper is the antiquated terminology.
– Yuval Filmus
Sep 26 at 15:54
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f97746%2fis-there-a-polynomial-time-algorithm-to-tell-if-an-nfa-over-an-unary-alphabet-is%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
