{ "info": { "author": "Marcell J. Vazquez-Chanlatte", "author_email": "mvc@linux.com", "bugtrack_url": null, "classifiers": [ "License :: OSI Approved :: MIT License", "Programming Language :: Python :: 3", "Programming Language :: Python :: 3.6", "Programming Language :: Python :: 3.7" ], "description": "# L*\n\n[![Build Status](https://cloud.drone.io/api/badges/mvcisback/lstar/status.svg)](https://cloud.drone.io/mvcisback/lstar)\n[![codecov](https://codecov.io/gh/mvcisback/lstar/branch/master/graph/badge.svg)](https://codecov.io/gh/mvcisback/lstar)\n[![PyPI version](https://badge.fury.io/py/lstar.svg)](https://badge.fury.io/py/lstar)\n[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)\n\nImplementation of the discriminant tree L* algorithm DFA learning algorithm\nprovided in [^1].\n\n\n\n**Table of Contents**\n\n- [Installation](#installation)\n- [Usage](#usage)\n - [Label Queries](#label-queries)\n - [Equivalence Queries](#equivalence-queries)\n - [All together](#all-together)\n- [Learning Moore Machines and DFA-labelers](#learning-moore-machines-and-dfa-labelers)\n- [Testing](#testing)\n- [TODO](#todo)\n- [Footnotes](#footnotes)\n\n\n\n\n\n# Installation\n\nIf you just need to use `lstar`, you can just run:\n\n`$ pip install lstar`\n\nFor developers, note that this project uses the\n[poetry](https://poetry.eustace.io/) python package/dependency\nmanagement tool. Please familarize yourself with it and then\nrun:\n\n`$ poetry install`\n\n# Usage\n\nThe main entry point for using this library is the `learn_dfa`\nfunction.\n\n```python\nfrom lstar import learn_dfa\n```\n\nThis function requires the arguments:\n```python\ndfa = learn_dfa(\n inputs= .. , # Inputs over which the target concept is over.\n # Note: Sequence of Hashables.\n\n label=.., # Function answering whether a given word is in the target\n # language.\n #\n # Tuple[Alphabet] -> bool\n\n find_counter_example=.., # Function which takes a hypothesis DFA\n # and either returns None or a counter example,\n # i.e., an element misclassified by hypothesis\n # DFA.\n #\n # DFA -> Union[Tuple[Alphabet], None]\n\n)\n```\n\nBelow is an example of learning following language over `{0, 1}`:\n\n\n> The number of 1's in the word is a multiple of 4.\n\n\n## Label Queries\n\nWe start by defining the label query function. \n\n**Note** that this implementation of `lstar` assumes that this\nfunction is either cheap (`O(1)`-ish) to call or is memoized.\n\n\n```python\nfrom functools import lru_cache\n\n@lru_cache(maxsize=None) # Memoize member queries \ndef is_mult_4(word):\n \"\"\"Want to learn 4 state counter\"\"\"\n return (sum(word) % 4) == 0\n```\n\n## Equivalence Queries\n\nNext you need to define a function which given a candidate `DFA`\nreturns either a counter example that this `DFA` mislabels or `None`.\n\nNote that the `DFA` type used comes from the `dfa` package\n([link](https://github.com/mvcisback/dfa)).\n\n`lstar` provides two functions to make writing counterexample oracles \neasier.\n\n1. `validate_ce`: Takes a counterexample oracle and retries \n if returned \"counterexample\" is not actually a counterexample.\n Useful if using heuristic solver or asking a human.\n\n ```python\n from lstar import validate_ce\n\n @validate_ce(is_mult_4, retry=True)\n def ask_human(dfa):\n ...\n ```\n2. `iterative_deeping_ce`: This function performs an iterative\n deepening traversal of the candidate dfa and see's if it matches\n the labeler on all tested words.\n\n ```python\n from lstar import iterative_deeping_ce\n\n find_ce = iterative_deeping_ce(is_mult_4, depth=10)\n ```\n\n\n## All together\n\n```python\ndfa = learn_dfa(\n inputs={0, 1}, # Possible inputs.\n label=is_mult_4, # Does this sequence belong in the language.\n find_counter_example=iterative_deeping_ce(is_mult_4, depth=10)\n)\n\nassert not dfa.label(())\nassert not dfa.label((1,))\nassert not dfa.label((1, 1, ))\nassert dfa.label((1, 1, 1))\nassert dfa.label((1, 1, 0, 1))\n```\n\n# Learning Moore Machines and DFA-labelers\n\nBy default, `learn_dfa` learns as Deterministic Finite Acceptor;\nhowever, by specifying the `outputs` parameter and adjusting the\n`label` function, one can learn a Deterministic Finite Labeler\n(which is isomorphic to a Moore Machine). \n\nFor example, the 4 state counter from before can be modified to output\nthe current count rather than whether or not the word sums to a\nmultiple of 4.\n\n\n```python\ndef sum_mod_4(state):\n return sum(state) % 4\n\ndfl = learn_dfa(\n inputs={0, 1},\n label=sum_mod_4,\n find_counter_example=ask_human,\n outputs={0, 1, 2, 3},\n) # Returns a Deterministic Finite Labeler.\n\nassert dfl.label(()) == 0\nassert dfl.label((1,)) == 1\nassert dfl.label((1, 1, )) == 2\nassert dfl.label((1, 1, 1)) == 3\nassert dfl.label((1, 1, 0, 1)) == 3\nassert dfl.label((1, 1, 1, 1)) == 0\n```\n\nThe deterministic labeler can be interpreted as a moore machine by\nusing the `transduce` method rather than `label`.\n\n```python\nassert dfl.transduce(()) == ()\nassert dfl.transduce((1,)) == (0,)\nassert dfl.transduce((1, 1, )) == (0, 1)\nassert dfl.transduce((1, 1, 1)) == (0, 1, 2)\nassert dfl.transduce((1, 1, 0, 1)) == (0, 1, 2, 2)\nassert dfl.transduce((1, 1, 1, 1, 1)) == (0, 1, 2, 3, 0)\n```\n\n\n# Testing\n\nThis project uses pytest. Simply run\n\n`$ poetry run pytest`\n\nin the root of the repository.\n\n# Similar Libraries\n## Python Based\n 1. https://github.com/steynvl/inferrer : DFA learning\n library supporting active and passive dfa learning. Active\n learning is based on L* with an observation table. Also\n supports learning NFAs.\n\n 1. https://gitlab.lis-lab.fr/dev/scikit-splearn/ : Library for learning\n weighted automata via the spectral method.\n\n 1. https://pypi.org/project/pylstar/ : Another L* based DFA\n learning library.\n\n## Java Based\n 1. https://learnlib.de/ : State of the art automata learning\n toolbox. Supports passive and active learning algorithms for DFAs,\n Mealy Machines, and Visibly Push Down Automata.\n 1. https://github.com/lorisdanto/symbolicautomata : Library for\n symbolic automata and symbolic visibly pushdown automata.\n\n# Footnotes\n\n[^1]: Kearns, Michael J., Umesh Virkumar Vazirani, and Umesh Vazirani. An introduction to computational learning theory. MIT press, 1994.\n", "description_content_type": "text/markdown", "docs_url": null, "download_url": "", "downloads": { "last_day": -1, "last_month": -1, "last_week": -1 }, "home_page": "", "keywords": "", "license": "MIT", "maintainer": "Marcell J. Vazquez-Chanlatte", "maintainer_email": "mvc@linux.com", "name": "lstar", "package_url": "https://pypi.org/project/lstar/", "platform": "", "project_url": "https://pypi.org/project/lstar/", "project_urls": null, "release_url": "https://pypi.org/project/lstar/0.2.8/", "requires_dist": [ "funcy (>=1.12,<2.0)", "attrs (>=19.1,<20.0)", "lazytree (>=0.3.0,<0.4.0)", "dfa (>=0.3.1,<0.4.0)" ], "requires_python": ">=3.6,<4.0", "summary": "Python implementation of lstar automata learning algorithm.", "version": "0.2.8" }, "last_serial": 5574768, "releases": { "0.1.0": [ { "comment_text": "", "digests": { "md5": "fa08eb3703d8282c6614af46864e4c49", "sha256": "e1fcca6dbfebd113ca175c287b92335f7dc65a7580e891dbdd43bc65343eab4c" }, "downloads": -1, "filename": "lstar-0.1.0-py2.py3-none-any.whl", "has_sig": false, "md5_digest": "fa08eb3703d8282c6614af46864e4c49", "packagetype": "bdist_wheel", "python_version": "py2.py3", "requires_python": null, "size": 4678, "upload_time": "2019-04-15T21:15:17", "url": "https://files.pythonhosted.org/packages/f8/5e/ea19edc1fcf394ca9dab87d44f1ed3f009cb2fd8cc0ea49e8c7fc096db33/lstar-0.1.0-py2.py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "74b0a0fb028465105e3aa43e8e151c91", "sha256": "51beb9646fe922b1cc76929b9f5f0d6033669da38198beae66c68dd644682b81" }, "downloads": -1, "filename": "lstar-0.1.0.tar.gz", "has_sig": false, "md5_digest": "74b0a0fb028465105e3aa43e8e151c91", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 2780, "upload_time": "2019-04-15T21:15:24", "url": "https://files.pythonhosted.org/packages/bb/37/328fbed99eba7e1d7a54abb613d3cf0f54a46cd283ad53e1d556939ae115/lstar-0.1.0.tar.gz" } ], "0.1.1": [ { "comment_text": "", "digests": { "md5": "654d1939917eec2eb31ea3e34f7a2268", "sha256": "ab9e61f4d3ed15d73aaf68f7985e39c0c13fc92adc9e56c895cfd619bd732ecc" }, "downloads": -1, "filename": "lstar-0.1.1-py3-none-any.whl", "has_sig": false, "md5_digest": "654d1939917eec2eb31ea3e34f7a2268", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": ">=3.6,<4.0", "size": 4349, "upload_time": "2019-06-09T04:17:45", "url": "https://files.pythonhosted.org/packages/2e/57/56de60966bc2a000a6390324d2598d85d71c0ce013ea83c0e3c22d4dc38c/lstar-0.1.1-py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "c9dbf68228e9952eda94964803c8a2e6", "sha256": "912aeb11d4a86aa0bdef01d2342585df2cd7b8f94d56edbe6b87b0a48fad8241" }, "downloads": -1, "filename": "lstar-0.1.1.tar.gz", "has_sig": false, "md5_digest": "c9dbf68228e9952eda94964803c8a2e6", "packagetype": "sdist", "python_version": "source", "requires_python": ">=3.6,<4.0", "size": 3327, "upload_time": "2019-06-09T04:17:46", "url": "https://files.pythonhosted.org/packages/69/ec/6cb5e583751cf0b3fccf40e6e74201dc4d78af9768bedd695b9605de746a/lstar-0.1.1.tar.gz" } ], "0.2.1": [ { "comment_text": "", "digests": { "md5": "b116028024df06f2e62533cd40e90bef", "sha256": "e5783606e0613938800437166648218c4cfc05292488d6852215863145f16e91" }, "downloads": -1, "filename": "lstar-0.2.1-py3-none-any.whl", "has_sig": false, "md5_digest": "b116028024df06f2e62533cd40e90bef", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": ">=3.7,<4.0", "size": 5074, "upload_time": "2019-06-24T22:53:26", "url": "https://files.pythonhosted.org/packages/b8/57/7d7b42cdef3a33b9e424eac8c7183e55c34487ecf3cc1de13ebe83093cc0/lstar-0.2.1-py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "16a575d50765104fc6f338459df8b340", "sha256": "fc0de1dfa9736aaabd3c9f12c1f6eb171f2c2ca1ba0120477c030a59b8024786" }, "downloads": -1, "filename": "lstar-0.2.1.tar.gz", "has_sig": false, "md5_digest": "16a575d50765104fc6f338459df8b340", "packagetype": "sdist", "python_version": "source", "requires_python": ">=3.7,<4.0", "size": 4074, "upload_time": "2019-06-24T22:53:28", "url": "https://files.pythonhosted.org/packages/71/86/c0aca72e15dab97d822ea01dfc5fb1f4e24fba7185d8777462f92c439376/lstar-0.2.1.tar.gz" } ], "0.2.3": [ { "comment_text": "", "digests": { "md5": "abaa29d494ca3763f7b97498e934b8fb", "sha256": "61ccd6c2e12db0f6fc4255456f5493b5012129eca1fa0f9660a9b5e4795e9878" }, "downloads": -1, "filename": "lstar-0.2.3-py3-none-any.whl", "has_sig": false, "md5_digest": "abaa29d494ca3763f7b97498e934b8fb", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": ">=3.7,<4.0", "size": 5591, "upload_time": "2019-07-04T05:26:03", "url": "https://files.pythonhosted.org/packages/e3/e6/125b7dfbf0e727915ae44a5f6de8120e2b577c0672bca31e40f603b95353/lstar-0.2.3-py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "abdc5094bbad06a1d5c91f25e464b5aa", "sha256": "1a93c8e264a50126bade7beebfb18e2283cb2231301f73882a928114bf0d5cc3" }, "downloads": -1, "filename": "lstar-0.2.3.tar.gz", "has_sig": false, "md5_digest": "abdc5094bbad06a1d5c91f25e464b5aa", "packagetype": "sdist", "python_version": "source", "requires_python": ">=3.7,<4.0", "size": 4334, "upload_time": "2019-07-04T05:26:04", "url": "https://files.pythonhosted.org/packages/63/0f/92406117239bd695f628a7f7e6e53e5113825df397b1b6f6c3125c9659b2/lstar-0.2.3.tar.gz" } ], "0.2.4": [ { "comment_text": "", "digests": { "md5": "6cb3d3052dd4ddd40252da402eb728b6", "sha256": "e58facf1bb448e773e279192aea5b968df3fbe399224e2f8ee4aae7bfe68c30f" }, "downloads": -1, "filename": "lstar-0.2.4-py3-none-any.whl", "has_sig": false, "md5_digest": "6cb3d3052dd4ddd40252da402eb728b6", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": ">=3.7,<4.0", "size": 5624, "upload_time": "2019-07-04T20:27:08", "url": "https://files.pythonhosted.org/packages/05/17/b7c8f6756ed607189f729c8b0e2d746e3b916fff93367c10ba089f5671f1/lstar-0.2.4-py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "ecfe6e309857ce92c802cebb3175a90a", "sha256": "a41b614e4b3e94eb7bac4cb5cefe71cd30d44d4249433009c65d72102a13faee" }, "downloads": -1, "filename": "lstar-0.2.4.tar.gz", "has_sig": false, "md5_digest": "ecfe6e309857ce92c802cebb3175a90a", "packagetype": "sdist", "python_version": "source", "requires_python": ">=3.7,<4.0", "size": 4358, "upload_time": "2019-07-04T20:27:09", "url": "https://files.pythonhosted.org/packages/5e/7a/d1ad360fc0907e1ba709bfc40dfb15999f380f13fb94ab437af0630ec2de/lstar-0.2.4.tar.gz" } ], "0.2.5": [ { "comment_text": "", "digests": { "md5": "14de294968255d915055777331856868", "sha256": "e856c5c1b2052a782f793421dae4296c9067b4bcbb8dd365212de1ee2787c8e5" }, "downloads": -1, "filename": "lstar-0.2.5-py3-none-any.whl", "has_sig": false, "md5_digest": "14de294968255d915055777331856868", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": ">=3.7,<4.0", "size": 5718, "upload_time": "2019-07-08T19:20:08", "url": "https://files.pythonhosted.org/packages/1d/f5/7470165c0d38634de65482abecdff8e967390b36106be8bd0d943866e0df/lstar-0.2.5-py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "2f64ef4eee1e118666f581088213ea5a", "sha256": "27fb8dc328b0f8de47d7bc0f357923e07cefbe11953ad32021ca47b4d4f42fb6" }, "downloads": -1, "filename": "lstar-0.2.5.tar.gz", "has_sig": false, "md5_digest": "2f64ef4eee1e118666f581088213ea5a", "packagetype": "sdist", "python_version": "source", "requires_python": ">=3.7,<4.0", "size": 4465, "upload_time": "2019-07-08T19:20:10", "url": "https://files.pythonhosted.org/packages/e9/ee/b9390d1c5655615c1cf7d68c435fe02caa8914359ddaa7fda1e6864a9705/lstar-0.2.5.tar.gz" } ], "0.2.6": [ { "comment_text": "", "digests": { "md5": "520a245a4e528e84ad467619df463f27", "sha256": "021ec4e4554db12e7a87395755de23f22524cae37b53f2fb8988a8a6d2e05b14" }, "downloads": -1, "filename": "lstar-0.2.6-py3-none-any.whl", "has_sig": false, "md5_digest": "520a245a4e528e84ad467619df463f27", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": ">=3.7,<4.0", "size": 5718, "upload_time": "2019-07-08T19:26:16", "url": "https://files.pythonhosted.org/packages/23/00/c2483cdfab480b4ef12d8ba1a141caffbb588362e14ade3571932a5fb38c/lstar-0.2.6-py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "4b8efffe28bdd7ee6e3634bc080d7f07", "sha256": "7b26495f7e72245a3e54679546abaa8f0aee08979b22b0be96526ed55defcaa2" }, "downloads": -1, "filename": "lstar-0.2.6.tar.gz", "has_sig": false, "md5_digest": "4b8efffe28bdd7ee6e3634bc080d7f07", "packagetype": "sdist", "python_version": "source", "requires_python": ">=3.7,<4.0", "size": 4467, "upload_time": "2019-07-08T19:26:17", "url": "https://files.pythonhosted.org/packages/f7/a4/e8436333c42b55944d48babc1f8207915a7e5881fe2aa8e123c329cf6fe1/lstar-0.2.6.tar.gz" } ], "0.2.7": [ { "comment_text": "", "digests": { "md5": "3bc4e9a7cfff413fe10733c501cb3e9b", "sha256": "d5d7a272a5e92b5eeb43458c75bd5fef34b96b3669ae7be26373a4b92875a4b3" }, "downloads": -1, "filename": "lstar-0.2.7-py3-none-any.whl", "has_sig": false, "md5_digest": "3bc4e9a7cfff413fe10733c501cb3e9b", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": ">=3.6,<4.0", "size": 8203, "upload_time": "2019-07-18T02:55:14", "url": "https://files.pythonhosted.org/packages/d3/3e/4e47665453305c2d716a48eacb1aa65fd6c306d62bfeb87611db1a32d231/lstar-0.2.7-py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "dfd1131b1bb44516d34637d87bb0c993", "sha256": "8f1e6aa22b6f0c49930b373475dc5c8346a091d743059a8623924c81ebfe5ffc" }, "downloads": -1, "filename": "lstar-0.2.7.tar.gz", "has_sig": false, "md5_digest": "dfd1131b1bb44516d34637d87bb0c993", "packagetype": "sdist", "python_version": "source", "requires_python": ">=3.6,<4.0", "size": 8234, "upload_time": "2019-07-18T02:55:27", "url": "https://files.pythonhosted.org/packages/60/61/b33bdeb108000df726a93a5bca5eca4763c044ea26d2df033ff9ff795f97/lstar-0.2.7.tar.gz" } ], "0.2.8": [ { "comment_text": "", "digests": { "md5": "61a867121ed71f5be5256155b78499ad", "sha256": "c49065dc414680ccd3af29ba82644330d20b0e5d9857cbe006c5a4babe6caec9" }, "downloads": -1, "filename": "lstar-0.2.8-py3-none-any.whl", "has_sig": false, "md5_digest": "61a867121ed71f5be5256155b78499ad", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": ">=3.6,<4.0", "size": 8225, "upload_time": "2019-07-23T22:39:32", "url": "https://files.pythonhosted.org/packages/79/4e/6ef6872577d670b89ada34d83577a6bbb19cb117ddca4ab2290c4ad4990c/lstar-0.2.8-py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "8d596bdc972baaa367bd305b62300f92", "sha256": "bfa0722412b0aa7818615739b8276bf0d37152da8eb27ba8263f0081b0825c45" }, "downloads": -1, "filename": "lstar-0.2.8.tar.gz", "has_sig": false, "md5_digest": "8d596bdc972baaa367bd305b62300f92", "packagetype": "sdist", "python_version": "source", "requires_python": ">=3.6,<4.0", "size": 8256, "upload_time": "2019-07-23T22:39:34", "url": "https://files.pythonhosted.org/packages/58/02/1d7f64fd12f8c9cc6c0367b2f23d21821cd2552663ab9b793bce1fb69773/lstar-0.2.8.tar.gz" } ] }, "urls": [ { "comment_text": "", "digests": { "md5": "61a867121ed71f5be5256155b78499ad", "sha256": "c49065dc414680ccd3af29ba82644330d20b0e5d9857cbe006c5a4babe6caec9" }, "downloads": -1, "filename": "lstar-0.2.8-py3-none-any.whl", "has_sig": false, "md5_digest": "61a867121ed71f5be5256155b78499ad", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": ">=3.6,<4.0", "size": 8225, "upload_time": "2019-07-23T22:39:32", "url": "https://files.pythonhosted.org/packages/79/4e/6ef6872577d670b89ada34d83577a6bbb19cb117ddca4ab2290c4ad4990c/lstar-0.2.8-py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "8d596bdc972baaa367bd305b62300f92", "sha256": "bfa0722412b0aa7818615739b8276bf0d37152da8eb27ba8263f0081b0825c45" }, "downloads": -1, "filename": "lstar-0.2.8.tar.gz", "has_sig": false, "md5_digest": "8d596bdc972baaa367bd305b62300f92", "packagetype": "sdist", "python_version": "source", "requires_python": ">=3.6,<4.0", "size": 8256, "upload_time": "2019-07-23T22:39:34", "url": "https://files.pythonhosted.org/packages/58/02/1d7f64fd12f8c9cc6c0367b2f23d21821cd2552663ab9b793bce1fb69773/lstar-0.2.8.tar.gz" } ] }