[특허]Determining large-scale finite state machines using constraint relaxation

Determining large-scale finite state machines using constraint relaxation 원문보기

IPC분류정보
국가/구분	United States(US) Patent 등록
국제특허분류(IPC7판)	G06F-017/50
출원번호	US-0610662 (2012-09-11)
등록번호	US-8903699 (2014-12-02)
발명자 / 주소	Vanspauwen, Niels
출원인 / 주소	Synopsys, Inc.
대리인 / 주소	Fenwick & West LLP
인용정보	피인용 횟수 : 0 인용 특허 : 30

초록 ▼

A computer-implemented method of finite state machine using constraint relaxation. A first expression having a plurality of variables is accessed. A second expression is accessed that describes a constraint with respect to a first variable of the plurality of variables. At least one of the variables from the second expression is eliminated to create a third expression with the constraint relaxed. The third expression is applied to the first expression to determine a finite state machine for the first expression.

대표청구항 ▼

1. A computer-implemented method for generating finite state machines comprising: accessing a first expression comprising a plurality of variables;accessing a second expression that describes a constraint with respect to a first variable of the plurality of variables of the first expression;eliminating, by a computer, at least one variable from the second expression to generate a third expression, the at least one variable being unnecessary for computing the first expression; anddetermining a finite state machine for the first expression based on the first expression and the third expression. 2. The method of claim 1, wherein determining the finite state machine comprises eliminating at least one input combination of possible input combinations to the finite state machine. 3. The method of claim 1, wherein eliminating at least one variable from the second expression comprises normalizing the second expression to produce a normalized expression. 4. The method of claim 3, wherein eliminating at least one variable from the second expression comprises applying a set of relaxation rules to the normalized expression to remove a variable from the normalized expression. 5. The method of claim 4, wherein the variable is a Boolean variable. 6. The method of claim 4, wherein the variable is an integer variable. 7. The method of claim 1, further comprising collapsing multiple states to a single state in the finite state machine by merging states that transition to a common state and for which inputs and outputs are identical. 8. The method of claim 7, further comprising traversing the finite state machine from end to start to collapse additional states. 9. A system comprising: a processor; anda non-transitory computer readable medium configured to store instructions, the instructions when executed by the processor cause the processor to perform a method comprising: accessing a first expression comprising a plurality of variables;accessing a second expression that describes a constraint with respect to a first variable of said plurality of variables of the first expression;eliminating at least one variable from the second expression to create a third expression, the at least one variable being unnecessary for computing the first expression; anddetermining a finite state machine for the first expression based on the first expression and the third expression. 10. The system of claim 9, wherein determining the finite state machine comprises eliminating at least one input combination of possible input combinations to the finite state machine. 11. The system of claim 9, wherein eliminating at least one variable from the second expression comprises normalizing the second expression to produce a normalized expression. 12. The system of claim 11, wherein eliminating at least one variable from the second expression comprises applying a set of relaxation rules to the normalized expression to remove a variable from the normalized expression. 13. The system of claim 12, wherein the variable is a Boolean variable. 14. The system of claim 12, wherein the variable is an integer variable. 15. The system of claim 9, wherein said method further comprises collapsing multiple states to a single state in the finite state machine by merging states that transition to a common state and for which inputs and outputs are identical. 16. The system of claim 15, wherein said method further comprises traversing the finite state machine from end to start to collapse additional states. 17. A non-transitory computer readable medium comprising stored instructions, the instructions when executed by at least one processor causes the processor to: access a first expression comprising a plurality of variables;access a second expression that describes a constraint with respect to a first variable of said plurality of variables of the first expression;eliminate at least one variable from the second expression to create a third expression, wherein the at least one variable is unnecessary for computing the first expression; anddetermine a finite state machine for the first expression based on the first expression and the third expression. 18. The computer readable medium claim 17, wherein the instruction to determine the finite state machine for the first expression further comprises an instruction to eliminate at least one input combination of possible input combinations to the finite state machine. 19. The computer readable medium claim 17, wherein the instruction to eliminate at least one variable from the second expression further comprises an instruction to normalize the second expression to produce a normalized expression. 20. The computer readable medium of claim 19 wherein the instruction to eliminate at least one variable from the second expression further comprises an instruction to apply a set of relaxation rules to the normalized expression to remove a variable from the normalized expression. 21. The computer readable medium of claim 20, wherein the variable is one of a Boolean variable and an integer variable. 22. The computer readable medium of claim 17, wherein the instructions further comprise instructions to collapse multiple states to a single state in the finite state machine by merging states that transition to a common state and for which inputs and outputs are identical. 23. The computer readable medium of claim 22, wherein the instructions further comprise instructions to traverse the finite state machine from end to start to collapse additional states.

이 특허에 인용된 특허 (30)

Apfelbaum, Larry; Savage, Peter L.; Bell, Katrin, Analyzing an extended finite state machine system model.
상세보기
Schwartz Edward L. ; Gormish Michael J., Apparatus and method for finite state machine coding of information selecting most probable state subintervals.
상세보기
Masuda Atsushi,JPX ; Sekine Masatoshi,JPX ; Hansen Jeffery P.,JPX, Apparatus and method for high-level synthesis of a logic circuit.
상세보기
Jay Christian Y.,FRX ; Poirot Franck J.,FRX, Automatic generation of test vectors for sequential circuits.
상세보기
Yu Tonny Kai Tong ; Chang Shir-Shen ; O'Neil Janet Lynn, Computer model of a finite state machine having inputs, outputs, delayed inputs and delayed outputs.
상세보기
Kanno Yuji (Tokyo JPX), Constructing method of finite-state machine performing transitions according to a partial type of success function and a.
상세보기
Vanspauwen, Niels, Determining large-scale finite state machines using constraint relaxation.
상세보기
Arcidiacono, Liliana; Matranga, Vincenzo, Fabrication method for a control unit for electronic microcontrollers or micoprocessors.
상세보기
Morse, Douglas C., Finite state machine with associated memory.
상세보기
Otsubo, Motohide, Function synthesizing method and apparatus, and recording medium on which program of said method is recorded.
상세보기
Vanspauwen, Niels, Large scale finite state machines.
상세보기
Iwashita Hiroaki,JPX ; Nakata Tsuneo,JPX, Logical device verification method and apparatus.
상세보기
Sun Xiao (Austin TX) Hull Carmie A. (Austin TX), Method and apparatus for constructing verification test sequences by merging and touring hierarchical unique input/outpu.
상세보기
Cheng Kwang-Ting (Santa Barbara CA) Krishnakumar Anjur S. (Rocky Hill NJ), Method and apparatus for determining the reachable states in a hybrid model state machine.
상세보기
Kita Ronald Allen ; Trumpler Mark Edward ; Elkind Lois Scirocco, Method and apparatus for generating an extended finite state machine architecture for a software specification.
상세보기
James Andrew Garrard Seawright, Method and apparatus for optimized partitioning of finite state machines synthesized from hierarchical high-level descriptions.
상세보기
Kita Ronald Allen ; Trumpler Mark Edward ; Elkind Lois Scirocco, Method and apparatus for testing implementations of software specifications.
상세보기
Steinz Hendrik Christian,NLX ; Dassel Johannes Roland,NLX, Method and device for processing signals in a protection system.
상세보기
Beer Ilan,ILX ; Eisner Cindy,ILX ; Rodeh Yoav,ILX, Method and system for reducing state space variables prior to symbolic model checking.
상세보기
Flora-Holmquist Alan Robert ; Morton Edward ; O'Grady James Day ; Staskauskas Mark Gerard, Method of and apparatus for constructing a complex control system and the complex control system created thereby.
상세보기
Wagner Ferdinand H. (24 Sterling Cir. ; Apt. 211 Wheaton IL 60187), Method of and apparatus for constructing a control system and control system created thereby.
상세보기
Giomi Jean-Charles, Method of extracting implicit sequential behavior from hardware description languages.
상세보기
Tamisier Thomas (St Germain en Laye FRX), Method of verification of a finite state sequential machine and resulting information support and verification tool.
상세보기
McElvain Kenneth S., Methods and apparatuses for automatic extraction of finite state machines.
상세보기
Petler Scott C., Minimizing logic by resolving "don't care" output values in a finite state machine.
상세보기
Herrera Ruben ; Sarpeshkar Rahul, Spike-triggered asynchronous finite state machine.
상세보기
Morley, Matthew John; Kashai, Yaron, System and method for compiling temporal expressions.
상세보기
Washabaugh Scott T. (Cary NC), System and method for designing a finite state machine to reduce power dissipation.
상세보기
Michael McNamara ; Chong Guan Tan ; Chiahon Chien ; David Todd Massey, System and method for identifying finite state machines and verifying circuit designs.
상세보기
Desai, Keyur B., Using and generating finite state machines to monitor system status.
상세보기

내보내기 메뉴

내보내기 구분

파일저장
인쇄
메일전송

구성항목

기본정보
상세정보

관리번호, 국가코드, 자료구분, 상태, 출원번호, 출원일자, 공개번호, 공개일자, 등록번호, 등록일자, 발명명칭(한글), 발명명칭(영문), 출원인(한글), 출원인(영문), 출원인코드, 대표IPC

저장형식

Text(ASCII format)
Excel format
PIAS분석(.xls)

메일정보

받는사람 (필수): @
보내는사람 (선택): @
제목
내용: KISTI 검색결과 이메일 서비스

안내

총 건의 자료가 검색되었습니다.

다운받으실 자료의 인덱스를 입력하세요. (1-10,000)

검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다.

데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요)

다운로드 파일은 UTF-8 형태로 저장됩니다.
파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오.

Text(ASCII format)
Excel format

AI-Helper ※ AI-Helper는 을 사용합니다.

AI-Helper

안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

IPC	Description
A	생활필수품
A62	인명구조; 소방(사다리 E06C)
A62B	인명구조용의 기구, 장치 또는 방법(특히 의료용에 사용되는 밸브 A61M 39/00; 특히 물에서 쓰이는 인명구조 장치 또는 방법 B63C 9/00; 잠수장비 B63C 11/00; 특히 항공기에 쓰는 것, 예. 낙하산, 투출좌석 B64D; 특히 광산에서 쓰이는 구조장치 E21F 11/00)
A62B-1/08	.. 윈치 또는 풀리에 제동기구가 있는 것

연합인증

Determining large-scale finite state machines using constraint relaxation 원문보기

초록 ▼

대표청구항 ▼

연구과제 타임라인

이 특허에 인용된 특허 (30)

관련 콘텐츠

특허 원문 보기

IPC 상위 출원인

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 국가코드, 자료구분, 상태, 출원번호, 출원일자, 공개번호, 공개일자, 등록번호, 등록일자, 발명명칭(한글), 발명명칭(영문), 출원인(한글), 출원인(영문), 출원인코드, 대표IPC 관리번호, 국가코드, 자료구분, 상태, 출원번호, 출원일자, 공개번호, 공개일자, 공고번호, 공고일자, 등록번호, 등록일자, 발명명칭(한글), 발명명칭(영문), 출원인(한글), 출원인(영문), 출원인코드, 대표출원인, 출원인국적, 출원인주소, 발명자, 발명자E, 발명자코드, 발명자주소, 발명자 우편번호, 발명자국적, 대표IPC, IPC코드, 요약, 미국특허분류, 대리인주소, 대리인코드, 대리인(한글), 대리인(영문), 국제공개일자, 국제공개번호, 국제출원일자, 국제출원번호, 우선권, 우선권주장일, 우선권국가, 우선권출원번호, 원출원일자, 원출원번호, 지정국, Citing Patents, Cited Patents
저장형식	Text(ASCII format) Excel format PIAS분석(.xls)
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

Determining large-scale finite state machines using constraint relaxation 원문보기

초록 ▼

대표청구항 ▼

연구과제 타임라인

전체(0) 논문(0) 특허(0) 보고서(0)

전체(0) 논문(0) 특허(0) 보고서(0)

이 특허에 인용된 특허 (30)

관련 콘텐츠

특허 원문 보기

IPC 상위 출원인

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트