• norsk
    • English
  • English 
    • norsk
    • English
  • Login
View Item 
  •   Home
  • Faculty of Mathematics and Natural Sciences
  • Department of Informatics
  • Department of Informatics
  • View Item
  •   Home
  • Faculty of Mathematics and Natural Sciences
  • Department of Informatics
  • Department of Informatics
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Regular Expressions with Numerical Constraints and Automata with Counters

Hovland, Dag
Chapter, Peer reviewed
Accepted version
Thumbnail
View/Open
Accepted version (313.3Kb)
URI
https://hdl.handle.net/1956/3628
Date
2009
Metadata
Show full item record
Collections
  • Department of Informatics [536]
Original version
In: Leucker, M.; Morgan, C. (eds.), Theoretical Aspects of Computing - ICTAC 2009: 231-245   https://doi.org/10.1007/978-3-642-03466-4_15
Abstract
Regular expressions with numerical constraints are an extension of regular expressions, allowing to bound numerically the number of times that a subexpression should be matched. Expressions in this extension describe the same languages as the usual regular expressions, but are exponentially more succinct. We de ne a class of nite automata with counters and a deterministic subclass of these. Deterministic nite automata with counters can rec- ognize words in linear time. Furthermore, we describe a subclass of the regular expressions with numerical constraints, a polynomial-time test for this subclass, and a polynomial-time construction of deterministic nite automata with counters from expressions in the subclass.
Description
Proceedings from the 6th International Colloquium Kuala Lumpur, Malaysia, August 16-20, 2009
Publisher
Springer
Series
Lecture Notes in Computer Science
5684
Copyright
Springer-Verlag

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit
 

 

Browse

ArchiveCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsDocument TypesJournalsThis CollectionBy Issue DateAuthorsTitlesSubjectsDocument TypesJournals

My Account

Login

Statistics

View Usage Statistics

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit