About: We investigate the membership problem that one may associate to every class of languages [Formula: see text]. The problem takes a regular language as input and asks whether it belongs to [Formula: see text]. In practice, finding an algorithm provides a deep insight on the class [Formula: see text]. While this problem has a long history, many famous open questions in automata theory are tied to membership. Recently, a breakthrough was made on several of these open questions. This was achieved by considering a more general decision problem than membership: covering. In the paper, we investigate how the new ideas and techniques brought about by the introduction of this problem can be applied to get new insight on earlier results. In particular, we use them to give new proofs for two of the most famous membership results: Schützenberger’s theorem and Simon’s theorem.   Goto Sponge  NotDistinct  Permalink

An Entity of Type : fabio:Abstract, within Data Space : covidontheweb.inria.fr associated with source document(s)

AttributesValues
type
value
  • We investigate the membership problem that one may associate to every class of languages [Formula: see text]. The problem takes a regular language as input and asks whether it belongs to [Formula: see text]. In practice, finding an algorithm provides a deep insight on the class [Formula: see text]. While this problem has a long history, many famous open questions in automata theory are tied to membership. Recently, a breakthrough was made on several of these open questions. This was achieved by considering a more general decision problem than membership: covering. In the paper, we investigate how the new ideas and techniques brought about by the introduction of this problem can be applied to get new insight on earlier results. In particular, we use them to give new proofs for two of the most famous membership results: Schützenberger’s theorem and Simon’s theorem.
subject
  • Algorithms
  • Automata (computation)
  • Mathematical logic
  • Theoretical computer science
  • Finnish musical groups
  • Computability theory
  • Formal languages
  • German-language surnames
  • Finite automata
  • Computational problems
  • MTV EMA winners
  • Alsatian-German people
  • French families
  • Warner Music Group artists
part of
is abstract of
is hasSource of
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software